本文共 5848 字，大约阅读时间需要 19 分钟。
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。 第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。 接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
对于每一个第一类操作，输出一个非负整数表示答案。
恩。。近来发现主席树真的可以做很多事情呢=。=
对于每一个节点建立主席树，记录从它到根节点的所有节点的权重，查询A->B的第k大即用A点主席树+B点主席树-LCA（A，B）的主席树-LCA（A，B）父亲的主席树。
主席树求第k大很简单吧。。
然后每次连边时我们暴力重建树，只是把小的树向大的树中插入。这个操作有个高端的名字*启发式合并*！！！
每次连边的时候顺便维护一下求lca要用的信息就好OwO。
只是记得要把不存在的父亲节点变成-1！！不然会有奇怪的错误TwT。。检查了我一个下午，大概就是本来一棵树的叶子节点被接在了另外一棵树上，那么它的有一些级的父亲会变得不存在TwT。
窝会在代码里标出来的。。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #define pritnf printf 17 #define scafn scanf 18 #define sacnf scanf 19 #define For(i,j,k) for(int i=(j);i<=(k);(i)++) 20 #define Clear(a) memset(a,0,sizeof(a)) 21 using namespace std; 22 typedef unsigned int Uint; 23 const int INF=0x3fffffff; 24 ///==============struct declaration============== 25 struct Node{ 26 Node *lc,*rc; 27 int siz; 28 Node (){lc=rc=NULL;siz=0;} 29 }; 30 ///==============var declaration================= 31 const int MAXN=100050; 32 Node rem[MAXN*100];int top=0; 33 #define new(Node) (&rem[top++]) 34 int N,M,T,TestCase,MaxVal; 35 int root[MAXN],val[MAXN],h[MAXN],Tree_siz[MAXN],depth[MAXN]; 36 int fa[MAXN][25]; 37 Node *node[MAXN],*null; 38 map mp; 39 vector Edge[MAXN]; 40 ///==============function declaration============ 41 void Init(); 42 void Insert(Node *&o,int l,int r,int k);//向一个单点线段树中k的地方+1 43 void Insert(Node *&prev,Node *&o,int l,int r,int k);//主席树k+1 44 void Merge(int A);//将以A为根的树全部挂到A父亲上去 45 //void Release(Node *&o);//释放空间，如果会超时就删掉 46 int lca(int x,int y);//返回x和y的lca 47 int Query(Node *&A1,Node *&A2,Node *&M1,Node *&M2,int l,int r,int rank);//查询A1和A2,M为LCA 48 int findr(int x){ return root[x] == x ? x : root[x] = findr(root[x]);} 49 void update(Node *&o); 50 ///==============main code======================= 51 int main() 52 { 53 #ifndef ONLINE_JUDGE 54 freopen("input","r",stdin); 55 freopen("output","w",stdout); 56 #endif 57 null=new(Node);null->lc=null->rc=null;node[0]=null; 58 Init();int lastans=0; 59 while (T--){ 60 char cmd; 61 do{ 62 scanf("%c",&cmd); 63 }while (cmd!='L'&&cmd!='Q'); 64 if (cmd=='L'){ 65 int x,y;scanf("%d%d",&x,&y);x^=lastans;y^=lastans; 66 int fx=findr(x),fy=findr(y); 67 if (Tree_siz[fx]>Tree_siz[fy]){ 68 swap(x,y); 69 swap(fx,fy); 70 } 71 Tree_siz[fy]+=Tree_siz[fx];root[fx]=fy; 72 fa[x][0]=y; 73 Edge[x].push_back(y);Edge[y].push_back(x); 74 Merge(x); 75 } 76 else if (cmd=='Q'){ 77 int x,y,k;scanf("%d%d%d",&x,&y,&k); 78 x^=lastans;y^=lastans;k^=lastans; 79 int LCA=lca(x,y); 80 lastans=Query(node[x],node[y],node[LCA],fa[LCA][0]==-1?null:node[fa[LCA][0]],1,MaxVal,k); 81 lastans=h[lastans]; 82 printf("%d\n",lastans); 83 } 84 } 85 return 0; 86 } 87 ///================fuction code==================== 88 void Init(){ 89 scanf("%d%d%d%d",&TestCase,&N,&M,&T); 90 for(int i=1;i<=N;i++){ //读入 91 scanf("%d",val+i);;h[i]=val[i]; 92 root[i]=i;Tree_siz[i]=1;depth[i]=1; 93 node[i]=new(Node); 94 } 95 memset(fa,-1,sizeof(fa)); 96 sort(h+1,h+1+N); 97 MaxVal=unique(h+1,h+1+N)-h-1; 98 for(int i=1;i<=MaxVal;i++)//离散化 99 mp[h[i]]=i;100 for(int i=1;i<=N;i++)101 val[i]=mp[val[i]];102 for(int i=1;i<=N;i++)//初始化节点103 Insert(node[i],1,MaxVal,val[i]);104 for(int i=1;i<=M;i++){ //连边105 int x,y;scanf("%d%d",&x,&y);106 int fx=findr(x),fy=findr(y);107 if (Tree_siz[fx]>Tree_siz[fy]){108 swap(fx,fy);109 swap(x,y);110 }111 Tree_siz[fy]+=Tree_siz[fx];112 root[fx]=fy;//合并两棵树=。=113 Edge[y].push_back(x);Edge[x].push_back(y);114 fa[x][0]=y;115 Merge(x);116 }117 }118 void Merge(int A){ //将以A为根的树全部重建119 //Release(node[A]);120 Insert(node[fa[A][0]==-1?0:fa[A][0]],node[A],1,MaxVal,val[A]);//将A建树=。=考虑要不要释放空间TAT121 depth[A]=depth[fa[A][0]==-1?0:fa[A][0]]+1;122 for(int i=1;(1< <=N;i++){ //更新lca信息123 int rt=fa[A][i-1];124 if (rt!=-1)125 fa[A][i]=fa[rt][i-1];126 else127 fa[A][i]=-1;///就是这里！！！！！！！不然它还会是原来的父亲！！！！！128 }129 int siz=Edge[A].size();130 for(int i=0;i =0;i--)146 if (fa[x][i]!=fa[y][i]&&fa[x][i]!=-1&&fa[y][i]!=-1){147 x=fa[x][i];148 y=fa[y][i];149 }150 return fa[x][0];151 }152 int Query(Node *&A1,Node *&A2,Node *&M1,Node *&M2,int l,int r,int rank){153 if (l==r) return l;154 if (A1==NULL) A1=null;155 if (A2==NULL) A2=null;156 if (M1==NULL) M1=null;157 if (M2==NULL) M2=null;158 int ls=0;159 if (M1->lc!=NULL) ls-=M1->lc->siz;160 if (M2->lc!=NULL) ls-=M2->lc->siz;161 if (A1->lc!=NULL) ls+=A1->lc->siz;162 if (A2->lc!=NULL) ls+=A2->lc->siz;163 int m=(l+r)>>1;164 if (ls>=rank)165 return Query(A1->lc,A2->lc,M1->lc,M2->lc,l,m,rank);166 else167 return Query(A1->rc,A2->rc,M1->rc,M2->rc,m+1,r,rank-ls);168 }169 void Insert(Node *&o,int l,int r,int k){170 if (o==NULL) o=new(Node);171 if (l==r){172 o->siz++;173 return;174 }175 int m=(l+r)>>1;176 if (m>=k)177 Insert(o->lc,l,m,k);178 else179 Insert(o->rc,m+1,r,k);180 update(o);181 }182 void update(Node *&o){183 if (o==NULL) return;184 o->siz=0;185 if (o->lc!=NULL)186 o->siz+=o->lc->siz;187 if (o->rc!=NULL)188 o->siz+=o->rc->siz;189 }190 void Insert(Node *&prev,Node *&o,int l,int r,int k){191 if (prev==NULL) prev=null;192 if (o==NULL) o=new(Node);193 int m=(l+r)>>1;194 if (l==r){195 o->siz=prev->siz+1;196 return;197 }198 if (m>=k){199 o->rc=prev->rc;200 o->lc=new(Node);201 Insert(prev->lc,o->lc,l,m,k);202 }203 else{204 o->lc=prev->lc;205 o->rc=new(Node);206 Insert(prev->rc,o->rc,m+1,r,k);207 }208 update(o);209 }
马上就要省选了我还是这么蒻肿么办啊！！好口啪！！
转载于:https://www.cnblogs.com/Houjikan/p/4425543.html
