P4175 [CTSC2008]网络管理

如果没有修改就是简单主席树，有了修改的话因为主席树维护的是到根的一段路径，所以修改操作会修改子树，也就是连续的一段dfn
所以显然树套树一波就没了
极其好写
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n;
int W[80010],w[160010],m;
int K[80010],A[80010],B[80010],dep[80010];
int fir[80010],dis[160010],nxt[160010],id;
il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
int dfn[80010],siz[80010];
int rt[80010],ls[10000010],rs[10000010],sum[10000010],cnt;
int st[17][80010];
il vd dfs(int x,int fa=-1){
    dfn[x]=++dfn[0];siz[x]=1;
    for(int i=fir[x];i;i=nxt[i]){
        if(dis[i]==fa)continue;
        st[0][dis[i]]=x;
        dep[dis[i]]=dep[x]+1;
        dfs(dis[i],x);
        siz[x]+=siz[dis[i]];
    }
}
#define mid ((l+r)>>1)
il vd update(int&x,int l,int r,const int&p,const int&d){
    if(!x)x=++cnt;sum[x]+=d;if(l==r)return;
    if(p<=mid)update(ls[x],l,mid,p,d);
    else update(rs[x],mid+1,r,p,d);
}
#undef mid
il vd Update(int l,int r,int w,int d){
    while(l<=n)update(rt[l],1,m,w,d),l+=l&-l;
    while(r<=n)update(rt[r],1,m,w,-d),r+=r&-r;
}
il int LCA(int x,int y){
    if(dep[x]<dep[y])std::swap(x,y);
    int C=dep[x]-dep[y];
    for(int i=16;~i;--i)if(C&(1<<i))x=st[i][x];
    for(int i=16;~i;--i)if(st[i][x]^st[i][y])x=st[i][x],y=st[i][y];
    if(x^y)x=st[0][x];return x;
}
int main(){
    n=gi();
    int q=gi(),x,y;
    for(int i=1;i<=n;++i)W[i]=w[++m]=gi();
    for(int i=1;i<n;++i)x=gi(),y=gi(),link(x,y),link(y,x);
    for(int i=1;i<=q;++i){
        K[i]=gi(),A[i]=gi(),B[i]=gi();
        if(!K[i])w[++m]=B[i];
    }
    std::sort(w+1,w+m+1),m=std::unique(w+1,w+m+1)-w-1;
    for(int i=1;i<=n;++i)W[i]=std::lower_bound(w+1,w+m+1,W[i])-w;
    for(int i=1;i<=q;++i)if(!K[i])B[i]=std::lower_bound(w+1,w+m+1,B[i])-w;
    dfs(1);
    for(int i=1;i<17;++i)
        for(int j=1;j<=n;++j)
            st[i][j]=st[i-1][st[i-1][j]];
    for(int i=1;i<=n;++i)Update(dfn[i],dfn[i]+siz[i],W[i],1);
    for(int i=1;i<=q;++i)
        if(K[i]){
            x=A[i],y=B[i];int lca=LCA(x,y);
            if(dep[x]+dep[y]-2*dep[lca]+1<K[i]){puts("invalid request!");continue;}
            static int A[2333],B[2333],a,b;
            a=b=0;
            int l,r;
            r=dfn[x];while(r)B[++b]=rt[r],r-=r&-r;
            r=dfn[y];while(r)B[++b]=rt[r],r-=r&-r;
            r=dfn[lca];while(r)A[++a]=rt[r],r-=r&-r;
            if(lca!=1){r=dfn[st[0][lca]];while(r)A[++a]=rt[r],r-=r&-r;}
            l=1,r=m;
            while(l^r){
                int tot=0;
                for(int i=1;i<=a;++i)tot-=sum[rs[A[i]]];
                for(int i=1;i<=b;++i)tot+=sum[rs[B[i]]];
                if(K[i]>tot){
                    K[i]-=tot;
                    for(int i=1;i<=a;++i)A[i]=ls[A[i]];
                    for(int i=1;i<=b;++i)B[i]=ls[B[i]];
                    r=(l+r)>>1;
                }else{
                    for(int i=1;i<=a;++i)A[i]=rs[A[i]];
                    for(int i=1;i<=b;++i)B[i]=rs[B[i]];
                    l=((l+r)>>1)+1;
                }
            }
            printf("%d
",w[l]);
        }else Update(dfn[A[i]],dfn[A[i]]+siz[A[i]],W[A[i]],-1),Update(dfn[A[i]],dfn[A[i]]+siz[A[i]],W[A[i]]=B[i],1);
    return 0;
}
P4175 [CTSC2008]网络管理

相关推荐
