preli-dhaka-19-B

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
const int mxn = 1e5+5;
int par[mxn];

template<typename T> using orderedSet =
    tree<T, null_type, less_equal<T>, // less_equal for multiset
    rb_tree_tag, tree_order_statistics_node_update>;
orderedSet<int> os[mxn];

int find_par(int u) {
    if(par[u] == u) return u;
    return par[u] = find_par(par[u]);
}
void union_sets(int a,int b) {
    int x = find_par(a);
    int y = find_par(b);
    if(x != y) {
        if(os[x].size() < os[y].size()) swap(x, y); // setting os[x] = bigger_set, os[y] = smaller_set
        for(auto it=os[y].begin();it!=os[y].end();++it) { //copying elements, smaller to bigger one
            os[x].insert(*it);
        }
        par[y] = x;
    }
}
int search(int a, int l, int r) {
    int x=find_par(a);
    int n2 = os[x].order_of_key(r+1); // elements less than (r+1)
    int n1 = os[x].order_of_key(l); // elements less than l
    return n2-n1;
}

int main() {
    int a,b,n,T,cas=0,typ,t,l,r,q;
    scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&n, &q);
        for(int i=1;i<=n;++i) {
            par[i]=i;
            os[i].clear();
        }
        printf("Case %d:\n", ++cas);
        while(q--) {
            scanf("%d",&typ);
            if(typ==0) {
                scanf("%d %d",&a,&b);
                union_sets(a,b);
            }
            else if(typ==1) {
                scanf("%d %d",&a, &t);
                int x=find_par(a);
                os[x].insert(t);
            }
            else {
                scanf("%d %d %d",&a,&l,&r);
                int res = search(a,l,r);
                printf("%d\n", res);
            }
        }
        // for(int i=1;i<=n;++i) {
        //     printf("%d -> parent: %d, elements: ",i,par[i]);
        //     for(auto it=os[i].begin();it!=os[i].end();++it) printf("%d ", *it);
        //     printf("\n");
        // }
    }
    return 0;
}

/*
2
3 6
1 2 7
2 1 1 10
0 2 1
2 1 1 10
1 2 1
2 1 1 10
3 7
1 3 2
1 1 100
1 1 2
0 1 3
0 2 1
2 2 1 10
2 1 2 2
*/