3123: [Sdoi2013]森林
Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 3336 Solved: 978
[Submit][Status][Discuss]
Description
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
HINT
对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7 3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。这些权值中，第三小的为 2，输出 2，lastans变为2。对于第二个操作 Q 3 5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1 1 2 4 。这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。
Source
/*
平常这种题很常见的思路就是求出dfs序来，然后每次查询的时候就是在主席树上查询 x+y-lca-fa[lca] 的值就行了。
但是这个题要动态的给森林中加边，还是强制在线的，所以就需要考虑换一种方法来维护这个东西。
首先先dfs出每棵树来，然后对于link操作，可以启发式合并两个主席树。这里我们把主席树维护的dfs序变成维护每个点到根的这条路径。所里link的时候假设我们要把x合到y上，那么我们就边dfs x 这棵树，边用当前点的fa作为历史状态的root来更新当前点的root就行了。求lca的fa数组和deep数组在dfs的时候动态维护就行了。
复杂度： O(nlog2n)
*/
#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e5+;
const int M=2e7+;
const int inf=1e9;
int n,m,T,sz,num,ans,val[N],dep[N],siz[N],belong[N],fa[N][];bool flag[N];
struct edge{int u,v,next;}e[N<<];int tot,head[N];
int root[N],R[N],sum[M],ls[M],rs[M];
inline int read(){
int x=;char ch=getchar();
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x;
}
inline void add(int x,int y){
e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].next=head[y];head[y]=tot;
}
void insert(int &k,int last,int l,int r,int pos){
k=++sz;
sum[k]=sum[last]+;
if(l==r) return ;
ls[k]=ls[last];
rs[k]=rs[last];
int mid=l+r>>;
if(pos<=mid) insert(ls[k],ls[last],l,mid,pos);
else insert(rs[k],rs[last],mid+,r,pos);
}
void dfs(int x,int f,int now){
flag[x]=;siz[x]=;belong[x]=now;
for(int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];
insert(root[x],root[f],,inf,val[x]);
for(int i=head[x];i;i=e[i].next){
if(e[i].v!=f){
fa[e[i].v][]=x;
dep[e[i].v]=dep[x]+;
dfs(e[i].v,x,now);
siz[x]+=siz[e[i].v];
}
}
}
inline int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
int t=dep[a]-dep[b];
for(int i=;i<;i++){
if(t&(<<i)){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=;~i;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][];
}
int query(int l,int r,int x1,int x2,int x3,int x4,int pos){
if(l==r) return l;
int now=sum[ls[x1]]+sum[ls[x2]]-sum[ls[x3]]-sum[ls[x4]];
int mid=l+r>>;
if(now>=pos) return query(l,mid,ls[x1],ls[x2],ls[x3],ls[x4],pos);
return query(mid+,r,rs[x1],rs[x2],rs[x3],rs[x4],pos-now);
}
int main(){
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
T=read();n=read();m=read();T=read();
for(int i=;i<=n;i++) val[i]=read();
for(int i=,x,y;i<=m;i++) x=read(),y=read(),add(x,y);
for(int i=;i<=n;i++) if(!flag[i]) dfs(i,,++num),R[num]=i;
for(int x,y,z,anc;T--;){
char ch;
for(ch=getchar();ch!='Q'&&ch!='L';ch=getchar());
x=read();y=read();
x^=ans;y^=ans;
if(ch=='Q'){
z=read();z^=ans;
anc=lca(x,y);
ans=query(,inf,root[x],root[y],root[anc],root[fa[anc][]],z);
printf("%d\n",ans);
}
else{
if(siz[R[belong[x]]]>siz[R[belong[y]]]) swap(x,y);
add(y,x);
fa[x][]=y;
siz[R[belong[y]]]+=siz[R[belong[x]]];
dep[x]=dep[y]+;
dfs(x,y,belong[y]);
}
}
return ;
}
/*10
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll; #define setfire(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
#define fre(name) freopen(#name".txt","r",stdin);
#ifdef WIN32
#define LL "%lld"
#else
#define LL "%I64d"
#endif const int N=1e5+5;
int cas,n,m,t,ans,val[N],tv[N],stack[N],prev[N];bool vis[N];
struct edge{int v,next;}e[N<<1];int tot,head[N];
char s[50]; inline int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
inline void add(int x,int y){
e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].next=head[y];head[y]=tot;
}
inline void bfs(int S,int T){
int top=1;stack[top]=S;
memset(vis,0,(n+2));
memset(prev,0,(n+2)<<2);
while(top){
int x=stack[top--];
for(int i=head[x];i;i=e[i].next){
if(!vis[e[i].v]){
vis[e[i].v]=1;
prev[e[i].v]=x;
if(e[i].v==T) return ;
stack[++top]=e[i].v;
}
}
}
}
inline void calc(int S,int T,int rk){
tv[0]=0;
for(int i=T;i!=S;i=prev[i]) tv[++tv[0]]=val[i];tv[++tv[0]]=val[S];
nth_element(tv+1,tv+rk,tv+tv[0]+1);
printf("%d\n",ans=tv[rk]);
}
void init(){
tot=0;
memset(head,0,(n+2)<<2);
}
int main(){
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
//for(cas=read();init(),cas--;){
cas=read();
n=read();m=read();t=read();
for(int i=1;i<=n;i++) val[i]=read();
for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y);
for(int x,y,z;t--;){
scanf("%s",s);
if(s[0]=='Q'){
x=read();y=read();z=read();
x^=ans;y^=ans;z^=ans;
bfs(x,y);
calc(x,y,z);
}
else{
x=read();y=read();
x^=ans;y^=ans;
add(x,y);
}
}
// }
return 0;
} */
UPD.2017-04-24
/*
Name: forest
Copyright: @2016-2017 shenben
Author: shenben
Date: 24/04/17 14:56
Description: Algorithm chairman tree & Heuristic mergeing
*/
#include<cstdio>
//#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+;
const int M=N*;
struct edge{int v,next;}e[N<<];int tot,head[N];
int n,m,num,cnt,T,sz,a[N],b[N];char s[];
int siz[N],dep[N],fa[N][],R[N],belong[N];bool flag[N];
int root[N],ls[M],rs[M],sum[M];
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void add(int x,int y){
e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].next=head[y];head[y]=tot;
}
void insert(int &k,int last,int l,int r,int x){
k=++sz;
sum[k]=sum[last]+;
if(l==r) return ;
ls[k]=ls[last];
rs[k]=rs[last];
int mid=l+r>>;
if(x<=mid) insert(ls[k],ls[last],l,mid,x);
else insert(rs[k],rs[last],mid+,r,x);
}
int query(int l,int r,int x1,int x2,int x3,int x4,int K){
if(l==r) return l;
int mid=l+r>>;
int cnt=sum[ls[x1]]+sum[ls[x2]]-sum[ls[x3]]-sum[ls[x4]];
if(K<=cnt) return query(l,mid,ls[x1],ls[x2],ls[x3],ls[x4],K);
else return query(mid+,r,rs[x1],rs[x2],rs[x3],rs[x4],K-cnt);
}
void dfs(int x,int f,int now){
flag[x]=;siz[x]=;belong[x]=now;
for(int i=;i<;i++) fa[x][i]=fa[fa[x][i-]][i-];
int p=lower_bound(b+,b+cnt+,a[x])-b;
insert(root[x],root[f],,cnt,p);
for(int i=head[x];i;i=e[i].next){
if(e[i].v!=f){
fa[e[i].v][]=x;
dep[e[i].v]=dep[x]+;
dfs(e[i].v,x,now);
siz[x]+=siz[e[i].v];
}
}
}
inline int lca(int a,int b){
if(dep[a]<dep[b]) swap(a,b);
int t=dep[a]-dep[b];
for(int i=;i<;i++){
if(t&(<<i)){
a=fa[a][i];
}
}
if(a==b) return a;
for(int i=;~i;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][];
}
int main(){
freopen("forest.in","r",stdin);
freopen("forest.out","w",stdout);
/*int size=64<<20;
char *p=(char *)malloc(size)+size;
__asm__("movl %0,%%esp\n"::"r"(p));*/
T=read();n=read();m=read();T=read();
for(int i=;i<=n;i++) b[i]=a[i]=read();
sort(b+,b+n+);
cnt=unique(b+,b+n+)-(b+);
for(int i=,x,y;i<=m;i++) x=read(),y=read(),add(x,y);
for(int i=;i<=n;i++) if(!flag[i]) flag[i]=,dfs(i,,++num),R[num]=i;
for(int i=,x,y,z,anc,ans=;i<=T;i++){
scanf("%s",s);x=read()^ans;y=read()^ans;
if(s[]=='Q'){
anc=lca(x,y);z=read()^ans;
ans=query(,cnt,root[x],root[y],root[anc],root[fa[anc][]],z);
printf("%d\n",ans=b[ans]);
}
else{
if(siz[R[belong[x]]]>siz[R[belong[y]]]) swap(x,y);
add(x,y);
fa[x][]=y;
dep[x]=dep[y]+;
siz[R[belong[y]]]+=siz[R[belong[x]]];
dfs(x,y,belong[y]);
}
}
fclose(stdin);fclose(stdout);
return ;
}