（其实原题强制在线，要用主席树）

代码：

注意：

1.下标从0~n-1

2.kruskal重构树开始有n个节点，tot从n开始，++tot

#include
     
      #define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int M=400000+5;const int N=400000+5;const int inf=0x3f3f3f3f;int n,m,Q;struct edge{    int x,y;    int val;}b[M];bool cmp0(edge a,edge b){    return a.val
      
       b.val;}int fafa[2*N];struct kruskal{    struct node{        int nxt,to;    }e[2*N];    int hd[2*N],cnt;    int fin(int x){        return fafa[x]==x?x:fafa[x]=fin(fafa[x]);    }    void add(int x,int y){        e[++cnt].nxt=hd[x];        e[cnt].to=y;        hd[x]=cnt;    }    int tot;    void build(int typ){        for(reg i=1;i<=n;++i){            if(typ) val[i]=inf;            else val[i]=-inf;        }        tot=n;        for(reg i=1;i<=m;++i){            int k1=fin(b[i].x),k2=fin(b[i].y);    //        cout<<" edge "<
       
        <<" "<
        
         <<" :: "<
         
          <<" "<
          
           <
           
            =0;--j){ if(fa[p][j]){ if(val[fa[p][j]]<=lim) p=fa[p][j]; } } return p; }else{ //go >=lim for(reg j=19;j>=0;--j){ if(fa[p][j]){ if(val[fa[p][j]]>=lim) p=fa[p][j]; } } return p; } }}kt[2];//0:min tree;1:max tree;int num;struct po{ int x,y; bool friend operator <(po a,po b){ return a.x
           
          
         
        
       
      
     

 总结：

kruskal重构树，就是考虑在经过边权在一定范围内到达的区域的点的情况

这里就是简单查询连通性

两个重构树判交的“二维数点”问题的转化很巧妙！