BZOJ - 3123 森林 (可持久化线段树+启发式合并)

时间：2023-03-09 05:57:13
BZOJ - 3123 森林 (可持久化线段树+启发式合并)

题目链接

先把初始边建成一个森林，每棵树选一个根节点递归建可持久化线段树。当添加新边的时候，把结点数少的树暴力重构，以和它连边的那个点作为父节点继承线段树，并求出倍增数组。树的结点数可以用并查集来维护。总复杂度$O(nlog^2n)$。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int N=1e5+,inf=0x3f3f3f3f;

 int a[N],b[N],n2,hd[N],ne,n,m,nq,fa[N][],dep[N],siz[N],fa2[N],rt[N],ls[N*],rs[N*],val[N*],tot,vis[N];

 struct E {int v,nxt;} e[N<<];

 void addedge(int u,int v) {e[ne]= {v,hd[u]},hd[u]=ne++;}

 int fd(int x) {return ~fa2[x]?fa2[x]=fd(fa2[x]):x;}

 int mgg(int x,int y) {

     int fx=fd(x),fy=fd(y);

     if(fx==fy)return ;

     fa2[fx]=fy,siz[fy]+=siz[fx];

     return ;

 }

 #define mid ((l+r)>>1)

 int lca(int u,int v) {

     if(dep[u]<dep[v])swap(u,v);

     for(int i=; i>=&&dep[u]>dep[v]; --i)if(dep[fa[u][i]]>=dep[v])u=fa[u][i];

     if(u==v)return u;

     for(int i=; i>=; --i)if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];

     return fa[u][];

 }

 void upd(int& u,int v,int x,int l=,int r=n2) {

     if(!u)u=++tot;

     val[u]=val[v]+;

     if(l==r)return;

     if(x<=mid)upd(ls[u],ls[v],x,l,mid),rs[u]=rs[v];

     else upd(rs[u],rs[v],x,mid+,r),ls[u]=ls[v];

 }

 int qry(int u,int v,int w1,int w2,int k,int l=,int r=n2) {

     if(l==r)return l;

     int cnt=val[ls[u]]+val[ls[v]]-val[ls[w1]]-val[ls[w2]];

     return k<=cnt?qry(ls[u],ls[v],ls[w1],ls[w2],k,l,mid):qry(rs[u],rs[v],rs[w1],rs[w2],k-cnt,mid+,r);

 }

 void dfs(int u,int f,int d,int flag) {

     if(flag&&vis[u])return;

     vis[u]=;

     fa[u][]=f,dep[u]=d,rt[u]=,upd(rt[u],rt[f],a[u]);

     for(int i=; i<; ++i)fa[u][i]=fa[fa[u][i-]][i-];

     for(int i=hd[u]; ~i; i=e[i].nxt) {

         int v=e[i].v;

         if(v==f)continue;

         dfs(v,u,d+,flag);

     }

 }

 void mg(int u,int v) {

     if(siz[fd(u)]>siz[fd(v)])swap(u,v);

     addedge(u,v),addedge(v,u),mgg(u,v),dfs(u,v,dep[v]+,);

 }

 int main() {

     scanf("%*d");

     memset(hd,-,sizeof hd),ne=;

     memset(fa2,-,sizeof fa2);

     scanf("%d%d%d",&n,&m,&nq);

     for(int i=; i<=n; ++i)scanf("%d",&a[i]);

     for(int i=; i<=n; ++i)b[i-]=a[i];

     sort(b,b+n),n2=unique(b,b+n)-b;

     for(int i=; i<=n; ++i)a[i]=lower_bound(b,b+n2,a[i])-b+;

     for(int i=; i<=n; ++i)siz[i]=;

     while(m--) {

         int u,v;

         scanf("%d%d",&u,&v);

         addedge(u,v),addedge(v,u),mgg(u,v);

     }

     for(int i=; i<=n; ++i)dfs(i,,,);

     for(int last=; nq--;) {

         char ch;

         int u,v,k;

         scanf(" %c",&ch);

         if(ch=='Q') {

             scanf("%d%d%d",&u,&v,&k),u^=last,v^=last,k^=last;

             int w=lca(u,v),ans=b[qry(rt[u],rt[v],rt[w],rt[fa[w][]],k)-];

             printf("%d\n",ans),last=ans;

         } else {

             scanf("%d%d",&u,&v),u^=last,v^=last;

             mg(u,v);

         }

     }

     return ;

 }

相关文章