zcmimi's blog
查看原题

点击跳转

看题意想到了主席树和LCT

LCT套主席树可行,但是比较麻烦,我们用另一种方法

启发式合并+主席树(\mathcal{n \log^2 n})

每次将小的插入到大的,顺便更新倍增LCA

每个节点在父节点的基础上插入自身的值

即每个节点的主席树记录的是自身到根节点的路径

具体看代码

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
#define Fur(i,x,y) for(int i(x);i<=y;++i)
#define Fdr(i,x,y) for(int i(x);i>=y;--i)
#define fl(i,x) for(int i(head[x]),to;to=e[i].to,i;i=e[i].nxt)
il void SWAP(int &x,int &y){int t=x;x=y;y=t;}
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=80011;
struct node{int v,p;bool operator<(node t){return v<t.v;}}b[N];
int val[N],rnk[N];
int cnt=0,head[N];
int d[N],fa[N],f[17][N],siz[N];
int SZ=0,sz=0,RT[N],ls[N*600],rs[N*600],s[N*600];
bool v[N];
struct edge{int to,nxt;}e[N<<2];
il void add(int x,int y){e[++cnt].to=y;e[cnt].nxt=head[x];head[x]=cnt;}
int gf(int x){return (fa[x]==x)?x:(fa[x]=gf(fa[x]));}
void build(int &x,int l,int r){
    s[x=++sz]=0;
    if(l==r)return;
    int m=(l+r)>>1;
    build(ls[x],l,m);build(rs[x],m+1,r);
}
void ins(int &x,int pre,int l,int r,int v){
    s[x=++sz]=s[pre]+1;
    ls[x]=ls[pre];rs[x]=rs[pre];
    if(l==r)return;
    int m=(l+r)>>1;
    if(v<=m)ins(ls[x],ls[pre],l,m,v);
    else ins(rs[x],rs[pre],m+1,r,v);
}
int ask(int x,int y,int lca,int flca,int l,int r,int k){
    if(l==r)return val[l];
    int m=(l+r)>>1,sum=s[ls[x]]+s[ls[y]]-s[ls[lca]]-s[ls[flca]];
    if(k<=sum)return ask(ls[x],ls[y],ls[lca],ls[flca],l,m,k);
    else return ask(rs[x],rs[y],rs[lca],rs[flca],m+1,r,k-sum);
}
void dfs(int x,int F,int rt){
    ++siz[rt];
    d[x]=d[f[0][x]=fa[x]=F]+1;
    Fur(i,1,16)f[i][x]=f[i-1][f[i-1][x]];
    v[x]=1;
    ins(RT[x],RT[F],1,SZ,rnk[x]);
    fl(i,x)if(to!=F)dfs(to,x,rt);
}
il int lca(int x,int y){
    if(d[x]<d[y])SWAP(x,y);
    Fdr(i,16,0)if(d[f[i][x]]>=d[y])x=f[i][x];
    if(x==y)return x;
    Fdr(i,16,0)if(f[i][x]!=f[i][y])
        x=f[i][x],y=f[i][y];
    return f[0][x];
}
int main(){
    int n,m,q,lastans=0;
    in(n);
    in(n,m,q);
    Fur(i,1,n)in(b[i].v),b[i].p=i,fa[i]=i;
    std::sort(b+1,b+n+1);b[0].v=-(1<<30);
    Fur(i,1,n)val[rnk[b[i].p]=(SZ+=(b[i].v!=b[i-1].v))]=b[i].v;
    int x,y,k,t;char ch;
    Fur(i,1,m)in(x,y),add(x,y),add(y,x);
    build(RT[0],1,SZ);
    Fur(i,1,n)if(!v[i])dfs(i,0,i),fa[i]=i;
    while(q--){
        in(ch,x,y);
        x^=lastans;y^=lastans;
        if(ch=='Q'){
            in(k);k^=lastans;t=lca(x,y);
            out(lastans=ask(RT[x],RT[y],RT[t],RT[f[0][t]],1,SZ,k),ln);
        }
        else{
            add(x,y),add(y,x);
            if(siz[gf(x)]>siz[gf(y)])SWAP(x,y);
            dfs(x,y,gf(y));
        }
    }
    flush();
}
LG 3302 [SDOI2013]森林
comment评论
Search
search