并不敢说完全会了线段树合并，只是至少知道原理写法了。。。还是太菜了，每天被大佬吊锤qwq

我看到的几道线段树合并都是权值线段树的合并。这个算法适用范围应该只是01线段树的。

这两道算入门题了吧。。。

发现粘题面没人看（自己都懒得看），以后粘链接加题意吧。

给$n$个没有连边的带权点，动态加边，询问$u$所在连通块权值第$k$大的点是什么。$n \leq 1e5 , q\leq 3e5$

给定森林，点有点权有重复！，边有边权。询问$u$所在连通块，只能走边权小于$w$的边，可达的权值第$k$大的点编号！是什么。$n \leq 1e5 , m,q \leq 5e5$ 被坑的巨惨qwq

后面的离线一下，按边权从小到大加进去就和永无乡一样了。

并查集维护连通性，并将两个连通块的权值线段树合并。询问就是在所在连通块线段树二分找。$(O(nlogn))$

#include
      
       using namespace std;const int N=100010;inline int read(){    int r=0,c=getchar();    while(!isdigit(c))c=getchar();    while(isdigit(c))    r=r*10+c-'0',c=getchar();    return r;}int fa[N],rt[N],n,m;int find(int x){    return x==fa[x]?x:fa[x]=find(fa[x]);}struct Node{    int L,R,sum;}T[N*20];int sz;#define ls T[o].L#define rs T[o].Rvoid pullup(int o){    T[o].sum=T[ls].sum+T[rs].sum;}void ins(int &o,int l,int r,int v){    if(!o)o=++sz;    if(l==r){        T[o].sum=1;return;    }    int mid=l+r>>1;    if(v<=mid)ins(ls,l,mid,v);    else ins(rs,mid+1,r,v);    pullup(o);}int merge(int x,int y){    if(!x)return y;    if(!y)return x;    T[x].L=merge(T[x].L,T[y].L);    T[x].R=merge(T[x].R,T[y].R);    pullup(x);    return x;}int query(int o,int l,int r,int rk){    if(l==r)return l;    int mid=l+r>>1;    if(rk<=T[ls].sum)return query(ls,l,mid,rk);    else return query(rs,mid+1,r,rk-T[ls].sum);}void Link(int x,int y){    int u=find(x),v=find(y);    fa[u]=v;rt[v]=merge(rt[u],rt[v]);}int a[N],id[N];void init(){    n=read(),m=read();    for(int i=1;i<=n;i++)    a[i]=read(),id[a[i]]=fa[i]=i;    while(m--){        int u=read(),v=read();        fa[find(u)]=find(v);    }    for(int i=1;i<=n;i++)    ins(rt[find(i)],1,n,a[i]);}void solve(){    m=read();    char s[10];    while(m--){        scanf("%s",s);        if(s[0]=='B'){            int u=read(),v=read();            Link(u,v);        }        else{            int u=find(read()),rk=read();            if(T[rt[u]].sum
      

 

#include
      
       using namespace std;const int N=200010;const int M=500010;inline int read(){    int r=0,c=getchar();    while(!isdigit(c))c=getchar();    while(isdigit(c))    r=r*10+c-'0',c=getchar();    return r;}int n,m,q;struct Edge{    int u,v,w;    friend bool operator < (Edge p,Edge q){        return p.w
       
        >1)inline void pullup(int o){    T[o].sum=T[ls].sum+T[rs].sum;}void ins(int &o,int l,int r,int val){    if(!o)o=++sz;    if(l==r){        T[o].sum=1;return;    }    if(val<=mid)ins(ls,l,mid,val);    else ins(rs,mid+1,r,val);    pullup(o);}int query(int o,int l,int r,int rk){    if(l==r){        return t[l];    }    if(rk<=T[ls].sum)return query(ls,l,mid,rk);    else return query(rs,mid+1,r,rk-T[ls].sum);}int merge(int x,int y){    if(!x)return y;    if(!y)return x;    if(!T[x].L&&!T[x].R){        T[x].sum+=T[y].sum;        return x;    }    T[x].L=merge(T[x].L,T[y].L);    T[x].R=merge(T[x].R,T[y].R);    pullup(x);return x;}inline void Link(int x,int y){    x=find(x),y=find(y);    if(x==y)return;    fa[y]=x;    rt[x]=merge(rt[x],rt[y]);}void init(){    n=read(),m=read(),q=read();    for(int i=1;i<=n;i++)    h[i]=t[i]=read(),fa[i]=i;    sort(t+1,t+n+1);    for(int i=1;i<=n;i++){        h[i]=lower_bound(t+1,t+n+1,h[i])-t;        ins(rt[i],1,n,h[i]);    }    for(int i=1;i<=m;i++)    e[i].u=read(),e[i].v=read(),e[i].w=read();    sort(e+1,e+m+1);    for(int i=1;i<=q;i++)    a[i].u=read(),a[i].w=read(),a[i].k=read(),a[i].id=i;    sort(a+1,a+q+1,cmpw);}void solve(){    int now=1;    for(int i=1;i<=q;i++){        int lim=a[i].w,rk=a[i].k;        while(e[now].w<=lim&&now<=m){            Link(e[now].u,e[now].v);now++;        }        int u=find(a[i].u),siz=T[rt[u]].sum;        if(siz