Input
第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。
第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。
接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。
Output
对于每一个第一类操作，输出一个非负整数表示答案。
Sample Input
1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 L 0 7
Q 9 2 5 Q 6 1 6
Sample Output
2
2
1
4
2
2
1
4
2
思路
恩。。近来发现主席树真的可以做很多事情呢=。=
对于每一个节点建立主席树，记录从它到根节点的所有节点的权重，查询A->B的第k大即用A点主席树+B点主席树-LCA（A，B）的主席树-LCA（A，B）父亲的主席树。
主席树求第k大很简单吧。。
然后每次连边时我们暴力重建树，只是把小的树向大的树中插入。这个操作有个高端的名字*启发式合并*！！！
每次连边的时候顺便维护一下求lca要用的信息就好OwO。
只是记得要把不存在的父亲节点变成-1！！不然会有奇怪的错误TwT。。检查了我一个下午，大概就是本来一棵树的叶子节点被接在了另外一棵树上，那么它的有一些级的父亲会变得不存在TwT。
窝会在代码里标出来的。。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
///==============struct declaration==============
struct Node{
Node *lc,*rc;
int siz;
Node (){lc=rc=NULL;siz=;}
};
///==============var declaration=================
const int MAXN=;
Node rem[MAXN*];int top=;
#define new(Node) (&rem[top++])
int N,M,T,TestCase,MaxVal;
int root[MAXN],val[MAXN],h[MAXN],Tree_siz[MAXN],depth[MAXN];
int fa[MAXN][];
Node *node[MAXN],*null;
map <int,int> mp;
vector <int> Edge[MAXN];
///==============function declaration============
void Init();
void Insert(Node *&o,int l,int r,int k);//向一个单点线段树中k的地方+1
void Insert(Node *&prev,Node *&o,int l,int r,int k);//主席树k+1
void Merge(int A);//将以A为根的树全部挂到A父亲上去
//void Release(Node *&o);//释放空间，如果会超时就删掉
int lca(int x,int y);//返回x和y的lca
int Query(Node *&A1,Node *&A2,Node *&M1,Node *&M2,int l,int r,int rank);//查询A1和A2,M为LCA
int findr(int x){return root[x] == x ? x : root[x] = findr(root[x]);}
void update(Node *&o);
///==============main code=======================
int main()
{
#ifndef ONLINE_JUDGE
freopen("input","r",stdin);
freopen("output","w",stdout);
#endif
null=new(Node);null->lc=null->rc=null;node[]=null;
Init();int lastans=;
while (T--){
char cmd;
do{
scanf("%c",&cmd);
}while (cmd!='L'&&cmd!='Q');
if (cmd=='L'){
int x,y;scanf("%d%d",&x,&y);x^=lastans;y^=lastans;
int fx=findr(x),fy=findr(y);
if (Tree_siz[fx]>Tree_siz[fy]){
swap(x,y);
swap(fx,fy);
}
Tree_siz[fy]+=Tree_siz[fx];root[fx]=fy;
fa[x][]=y;
Edge[x].push_back(y);Edge[y].push_back(x);
Merge(x);
}
else if (cmd=='Q'){
int x,y,k;scanf("%d%d%d",&x,&y,&k);
x^=lastans;y^=lastans;k^=lastans;
int LCA=lca(x,y);
lastans=Query(node[x],node[y],node[LCA],fa[LCA][]==-?null:node[fa[LCA][]],,MaxVal,k);
lastans=h[lastans];
printf("%d\n",lastans);
}
}
return ;
}
///================fuction code====================
void Init(){
scanf("%d%d%d%d",&TestCase,&N,&M,&T);
for(int i=;i<=N;i++){//读入
scanf("%d",val+i);;h[i]=val[i];
root[i]=i;Tree_siz[i]=;depth[i]=;
node[i]=new(Node);
}
memset(fa,-,sizeof(fa));
sort(h+,h++N);
MaxVal=unique(h+,h++N)-h-;
for(int i=;i<=MaxVal;i++)//离散化
mp[h[i]]=i;
for(int i=;i<=N;i++)
val[i]=mp[val[i]];
for(int i=;i<=N;i++)//初始化节点
Insert(node[i],,MaxVal,val[i]);
for(int i=;i<=M;i++){//连边
int x,y;scanf("%d%d",&x,&y);
int fx=findr(x),fy=findr(y);
if (Tree_siz[fx]>Tree_siz[fy]){
swap(fx,fy);
swap(x,y);
}
Tree_siz[fy]+=Tree_siz[fx];
root[fx]=fy;//合并两棵树=。=
Edge[y].push_back(x);Edge[x].push_back(y);
fa[x][]=y;
Merge(x);
}
}
void Merge(int A){//将以A为根的树全部重建
//Release(node[A]);
Insert(node[fa[A][]==-?:fa[A][]],node[A],,MaxVal,val[A]);//将A建树=。=考虑要不要释放空间TAT
depth[A]=depth[fa[A][]==-?:fa[A][]]+;
for(int i=;(<<i)<=N;i++){//更新lca信息
int rt=fa[A][i-];
if (rt!=-)
fa[A][i]=fa[rt][i-];
else
fa[A][i]=-;///就是这里！！！！！！！不然它还会是原来的父亲！！！！！
}
int siz=Edge[A].size();
for(int i=;i<siz;i++){
int &e=Edge[A][i];
if (fa[A][]!=e){
fa[e][]=A;
Merge(e);
}
}
}
int lca(int x,int y){
if (depth[x]<depth[y]) swap(x,y);//x在下面TwT
int deltax=depth[x]-depth[y];
for(int i=;(<<i)<=deltax;i++)
if (deltax&(<<i))
x=fa[x][i];
if (x==y) return x;
for(int i=;i>=;i--)
if (fa[x][i]!=fa[y][i]&&fa[x][i]!=-&&fa[y][i]!=-){
x=fa[x][i];
y=fa[y][i];
}
return fa[x][];
}
int Query(Node *&A1,Node *&A2,Node *&M1,Node *&M2,int l,int r,int rank){
if (l==r) return l;
if (A1==NULL) A1=null;
if (A2==NULL) A2=null;
if (M1==NULL) M1=null;
if (M2==NULL) M2=null;
int ls=;
if (M1->lc!=NULL) ls-=M1->lc->siz;
if (M2->lc!=NULL) ls-=M2->lc->siz;
if (A1->lc!=NULL) ls+=A1->lc->siz;
if (A2->lc!=NULL) ls+=A2->lc->siz;
int m=(l+r)>>;
if (ls>=rank)
return Query(A1->lc,A2->lc,M1->lc,M2->lc,l,m,rank);
else
return Query(A1->rc,A2->rc,M1->rc,M2->rc,m+,r,rank-ls);
}
void Insert(Node *&o,int l,int r,int k){
if (o==NULL) o=new(Node);
if (l==r){
o->siz++;
return;
}
int m=(l+r)>>;
if (m>=k)
Insert(o->lc,l,m,k);
else
Insert(o->rc,m+,r,k);
update(o);
}
void update(Node *&o){
if (o==NULL) return;
o->siz=;
if (o->lc!=NULL)
o->siz+=o->lc->siz;
if (o->rc!=NULL)
o->siz+=o->rc->siz;
}
void Insert(Node *&prev,Node *&o,int l,int r,int k){
if (prev==NULL) prev=null;
if (o==NULL) o=new(Node);
int m=(l+r)>>;
if (l==r){
o->siz=prev->siz+;
return;
}
if (m>=k){
o->rc=prev->rc;
o->lc=new(Node);
Insert(prev->lc,o->lc,l,m,k);
}
else{
o->lc=prev->lc;
o->rc=new(Node);
Insert(prev->rc,o->rc,m+,r,k);
}
update(o);
}
BZOJ 3123
马上就要省选了我还是这么蒻肿么办啊！！好口啪！！