DSU paint

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <set>
#include <map>
#include <queue>
#include <unordered_map>


using namespace std;
//DSU
struct dsu
{
    vector<int> parent;
    vector<int> sz;
    vector<int> end;

    dsu(int n)
    {
        parent=vector<int>(n);
        end=vector<int>(n);
        for(int i=0;i<n;i++)
        {
            parent[i]=i;
            end[i]=i;
        }
        sz=vector<int>(n,1);
    }

    int find_(int x)
    {
        int root=x;
        while(root!=parent[root])
            root=parent[root];

        //Path compression
        while(parent[x]!=root)
        {
            int p=parent[x];
            parent[x]=root;
            x=p;
        }
        return root;
    }
    bool union_(int x,int y)
    {
        int X=find_(x);
        int Y=find_(y);
        // x and y are already in the same set
        if(X==Y)
            return false;
        // x and y are not in same set, so we merge them
        if(sz[X]<sz[Y])
            swap(X, Y);
        // merge yRoot into xRoot
        parent[Y]=X;
        sz[X]+=sz[Y];
        end[X]=max(end[X],end[Y]);
        return true;
    }
};

int main(){
    ios::sync_with_stdio(0);
    int n,q;
    cin>>n>>q;
    dsu uf(n+1);
    vector<int> answer(n,0);
    vector<pair<int, pair<int, int>>> queries(q);
    for(int i=0;i<q;i++)
    {
        cin>>queries[i].first>>queries[i].second.first>>queries[i].second.second;
    }

    reverse(queries.begin(), queries.end());

    for(int i=0;i<q;i++)
    {
        int l = queries[i].second.first;
        int r = queries[i].second.second;
        int c = queries[i].first;
        for (int v = uf.end[uf.find_(l)]; v <= r; v = uf.end[uf.find_(v)]) {
            answer[v] = c;
            uf.union_(v, v+1);
        }
    }
    for(int i=0;i<n;i++)
    {
        cout<<answer[i]<<" ";
    }


    return 0;
}
/*
 input:
 10
 5
 1 0 9
 2 8 9
 3 6 8
 4 0 6
 5 6 8
 output:
 4 4 4 4 4 4 5 5 5 2
 */