BZOJ3123[Sdoi2013]森林——主席树+LCA+启发式合并-白红宇

BZOJ3123[Sdoi2013]森林——主席树+LCA+启发式合并

阅读量：5127 次

发布时间：2019-06-13

本文共 2954 字，大约阅读时间需要 9 分钟。

题目描述

输入

第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。

第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。

接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。

输出

对于每一个第一类操作，输出一个非负整数表示答案。

样例输入

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

样例输出

提示

对于第一个操作 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。之后的操作类似。

　　这道题总共两个操作，没有连边操作就是，但有了连边操作可能会想到LCT。因为数据范围不大，所以可以用启发式合并将两棵树合并。每次连接x,y时，比较两棵树的大小，把小的那棵连到大的那棵上，然后更新小的那棵树上每个点的倍增数组，祖先(即大的那棵树的根)，深度及这个点所对应的线段树。每次查询时求出两个点的lca及lca的父节点，在主席树上直接查询即可。

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define mid (L+R)/2using namespace std;int cnt;int tot;int ans;int len;int a,b;int tcase;int n,m,q;char s[5];int x,y,z;int d[80010];int h[80010];int v[80010];map
              
               g;int to[200010];int vis[80010];int anc[80010];int size[80010];int l[20000010];int r[20000010];int next[200010];int head[200010];int f[80010][26];int sum[20000010];int root[2000010];void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}int lca(int x,int y){ if(d[x]
               
                =0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0];}int updata(int pre,int L,int R,int v){ int rt=++cnt; l[rt]=l[pre]; r[rt]=r[pre]; sum[rt]=sum[pre]+1; if(L==R) { return rt; } else { if(v<=mid) { l[rt]=updata(l[pre],L,mid,v); } else { r[rt]=updata(r[pre],mid+1,R,v); } } return rt;}int query(int x,int y,int fa,int anc,int L,int R,int k){ if(L==R) { return g[L]; } int num=sum[l[x]]+sum[l[y]]-sum[l[fa]]-sum[l[anc]]; if(k<=num) { return query(l[x],l[y],l[fa],l[anc],L,mid,k); } else { return query(r[x],r[y],r[fa],r[anc],mid+1,R,k-num); }}void dfs(int x,int fa,int ac){ vis[x]=1; anc[x]=ac; f[x][0]=fa; d[x]=d[fa]+1; root[x]=updata(root[fa],1,n,v[x]); for(int i=1;i<=23;i++) { f[x][i]=f[f[x][i-1]][i-1]; } for(int i=head[x];i;i=next[i]) { if(to[i]!=fa) { dfs(to[i],x,ac); size[x]+=size[to[i]]; } }}int main(){ scanf("%d",&tcase); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=n;i++) { scanf("%d",&v[i]); h[i]=v[i]; size[i]=1; } sort(h+1,h+1+n); len=unique(h+1,h+1+n)-h-1; for(int i=1;i<=n;i++) { int val=v[i]; v[i]=lower_bound(h+1,h+1+len,v[i])-h; g[v[i]]=val; } for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); } for(int i=1;i<=n;i++) { if(!vis[i]) { dfs(i,0,i); } } while(q--) { scanf("%s",s); if(s[0]=='Q') { scanf("%d%d%d",&x,&y,&z); x=x^ans; y=y^ans; z=z^ans; a=lca(x,y); b=f[a][0]; ans=query(root[x],root[y],root[a],root[b],1,n,z); printf("%d\n",ans); } else { scanf("%d%d",&x,&y); x=x^ans; y=y^ans; add(x,y); add(y,x); if(size[anc[x]]

转载于:https://www.cnblogs.com/Khada-Jhin/p/9305700.html

你可能感兴趣的文章