3123: [Sdoi2013]森林
Time Limit: 20 Sec Memory Limit: 512 MBSubmit: 3336 Solved: 978
[Submit][Status][Discuss]
Description
.jpg)
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。之后的操作类似。
.jpg)
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+5; const int M=2e7+5; const int inf=1e9; int n,m,T,sz,num,ans,val[N],dep[N],siz[N],belong[N],fa[N][20];bool flag[N]; struct edge{int u,v,next;}e[N<<1];int tot,head[N]; int root[N],R[N],sum[M],ls[M],rs[M]; 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; } void insert(int &k,int last,int l,int r,int pos){ k=++sz; sum[k]=sum[last]+1; if(l==r) return ; ls[k]=ls[last]; rs[k]=rs[last]; int mid=l+r>>1; if(pos<=mid) insert(ls[k],ls[last],l,mid,pos); else insert(rs[k],rs[last],mid+1,r,pos); } void dfs(int x,int f,int now){ flag[x]=1;siz[x]=1;belong[x]=now; for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; insert(root[x],root[f],1,inf,val[x]); for(int i=head[x];i;i=e[i].next){ if(e[i].v!=f){ fa[e[i].v][0]=x; dep[e[i].v]=dep[x]+1; 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=0;i<20;i++){ if(t&(1<<i)){ a=fa[a][i]; } } if(a==b) return a; for(int i=19;~i;i--){ if(fa[a][i]!=fa[b][i]){ a=fa[a][i]; b=fa[b][i]; } } return fa[a][0]; } 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>>1; if(now>=pos) return query(l,mid,ls[x1],ls[x2],ls[x3],ls[x4],pos); return query(mid+1,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=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 i=1;i<=n;i++) if(!flag[i]) dfs(i,0,++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(1,inf,root[x],root[y],root[anc],root[fa[anc][0]],z); printf("%d ",ans); } else{ if(siz[R[belong[x]]]>siz[R[belong[y]]]) swap(x,y); add(y,x); fa[x][0]=y; siz[R[belong[y]]]+=siz[R[belong[x]]]; dep[x]=dep[y]+1; dfs(x,y,belong[y]); } } return 0; } /*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 ",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+5; const int M=N*85; struct edge{int v,next;}e[N<<1];int tot,head[N]; int n,m,num,cnt,T,sz,a[N],b[N];char s[5]; int siz[N],dep[N],fa[N][20],R[N],belong[N];bool flag[N]; int root[N],ls[M],rs[M],sum[M]; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';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]+1; if(l==r) return ; ls[k]=ls[last]; rs[k]=rs[last]; int mid=l+r>>1; if(x<=mid) insert(ls[k],ls[last],l,mid,x); else insert(rs[k],rs[last],mid+1,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>>1; 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+1,r,rs[x1],rs[x2],rs[x3],rs[x4],K-cnt); } void dfs(int x,int f,int now){ flag[x]=1;siz[x]=1;belong[x]=now; for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; int p=lower_bound(b+1,b+cnt+1,a[x])-b; insert(root[x],root[f],1,cnt,p); for(int i=head[x];i;i=e[i].next){ if(e[i].v!=f){ fa[e[i].v][0]=x; dep[e[i].v]=dep[x]+1; 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=0;i<20;i++){ if(t&(1<<i)){ a=fa[a][i]; } } if(a==b) return a; for(int i=19;~i;i--){ if(fa[a][i]!=fa[b][i]){ a=fa[a][i]; b=fa[b][i]; } } return fa[a][0]; } 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 "::"r"(p));*/ T=read();n=read();m=read();T=read(); for(int i=1;i<=n;i++) b[i]=a[i]=read(); sort(b+1,b+n+1); cnt=unique(b+1,b+n+1)-(b+1); for(int i=1,x,y;i<=m;i++) x=read(),y=read(),add(x,y); for(int i=1;i<=n;i++) if(!flag[i]) flag[i]=1,dfs(i,0,++num),R[num]=i; for(int i=1,x,y,z,anc,ans=0;i<=T;i++){ scanf("%s",s);x=read()^ans;y=read()^ans; if(s[0]=='Q'){ anc=lca(x,y);z=read()^ans; ans=query(1,cnt,root[x],root[y],root[anc],root[fa[anc][0]],z); printf("%d ",ans=b[ans]); } else{ if(siz[R[belong[x]]]>siz[R[belong[y]]]) swap(x,y); add(x,y); fa[x][0]=y; dep[x]=dep[y]+1; siz[R[belong[y]]]+=siz[R[belong[x]]]; dfs(x,y,belong[y]); } } fclose(stdin);fclose(stdout); return 0; }