BZOJ-1146 [CTSC2008]网络管理Network

n+e posted @ 2015年7月02日 16:18 in BZOJ with tags 树状数组 主席树 , 13798 阅读

以前看到这题以为不可写,树链剖分+线段树套平衡树,3个log了还不如去写暴力。。。

然而仔细分析一下就是下面这样:

如果不带修改,就是Spoj 10628. Count on a tree

如果不是树是序列带修改,就是Zju2112 Dynamic Rankings

然后怎么做呢?

先把COT给做完,假设没修改只有询问的话;

然后处理出这颗树的dfs序,当我们对其中某一个点修改点权的时候,相当于把它子树内所有点的主席树所存的信息全部修改,对应到dfs序上就是一段区间,所以就要支持区间删减一个数;

想到了什么?就是ZJU那题!

所以现在已经很明了了,我们把两个部分(初始点权,修改后的点权)分开来记,前一部分用正常的主席树,后一部分用树状数组套主席树来进行前缀和优化。

/**************************************************************
    Problem: 1146
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1648 ms
    Memory:87964 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
#define N 80010
#define mid (l+r>>1)
int n,q,et=1,la[N],v[N],cnt=1,tot,y[N<<1],top[N],dfn,L[N],R[N],fa[N],son[N],siz[N],dep[N],root[N],tr[N],tmp0[N],tmp1[N],ltot,rtot;
struct E{int to,nxt;}e[N<<1];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
struct Q{int k,a,b;}a[N];
struct D{int x,n;}d[N<<1];
bool operator<(const D&a,const D&b){return a.x<b.x;}
struct T{int ls,rs,cnt;}t[N*83];
int bt(int g,int l,int r,int v,int p){
    int o=++tot;t[o]=t[g],t[o].cnt+=p;
    if(l<r)if(v<=mid)t[o].ls=bt(t[g].ls,l,mid,v,p);
    else t[o].rs=bt(t[g].rs,mid+1,r,v,p);
    return o;
}
void add(int x,int v,int p){
    for(;x<=n;x+=x&-x)tr[x]=bt(tr[x],1,cnt,v,p);
}
void dfs(int x,int f){
    siz[x]=1,dep[x]=dep[fa[x]=f]+1;
    for(int i=la[x];i;i=e[i].nxt)if(e[i].to!=f){
        dfs(e[i].to,x),siz[x]+=siz[e[i].to];
        if(siz[son[x]]<siz[e[i].to])son[x]=e[i].to;
    }
}
void dfs2(int x,int tp){
    top[x]=tp,L[x]=++dfn,root[x]=bt(root[fa[x]],1,cnt,v[x],1);
    if(son[x])dfs2(son[x],tp);
    for(int i=la[x];i;i=e[i].nxt)
    if(e[i].to!=fa[x]&&e[i].to!=son[x])dfs2(e[i].to,e[i].to);
    R[x]=dfn;
}
int lca(int x,int y){
    while(top[x]!=top[y])
    if(dep[top[x]]>dep[top[y]])x=fa[top[x]];else y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
void get(int x,int k){
    if(k){for(x?tmp1[++rtot]=root[x]:1,x=L[x];x;x-=x&-x)if(tr[x])tmp1[++rtot]=tr[x];}
    else {for(x?tmp0[++ltot]=root[x]:1,x=L[x];x;x-=x&-x)if(tr[x])tmp0[++ltot]=tr[x];}
}
int query(int k,int l,int r){
    int sum;
    while(l<r){
        sum=0;
        for(int i=1;i<=ltot;i++)sum-=t[t[tmp0[i]].rs].cnt;
        for(int i=1;i<=rtot;i++)sum+=t[t[tmp1[i]].rs].cnt;
        if(sum>=k){
            for(int i=1;i<=ltot;i++)tmp0[i]=t[tmp0[i]].rs;
            for(int i=1;i<=rtot;i++)tmp1[i]=t[tmp1[i]].rs;
            l=mid+1;
        }else{
            for(int i=1;i<=ltot;i++)tmp0[i]=t[tmp0[i]].ls;
            for(int i=1;i<=rtot;i++)tmp1[i]=t[tmp1[i]].ls;
            r=mid,k-=sum;
        }
    }
    return l;
}
int main(){
    n=F(),q=F();
    for(int i=1;i<=n;i++)d[++tot]=(D){v[i]=F(),i};
    for(int i=1,g,h;i<n;i++)g=F(),h=F(),adde(g,h),adde(h,g);
    for(int i=1;i<=q;i++)a[i]=(Q){F(),F(),F()},!a[i].k?d[++tot]=(D){a[i].b,i+n},1:1;
    std::sort(d+1,d+1+tot);d[tot+1].x=-1;
    for(int i=1;i<=tot;i++){
        if(d[i].n<=n)v[d[i].n]=cnt;else a[d[i].n-n].b=cnt;
        if(d[i].x!=d[i+1].x)y[cnt++]=d[i].x;
    }
    cnt--,tot=0,dfs(1,0),dfs2(1,1);
    for(int i=1,xx,yy,zz;i<=q;i++)
    if(!a[i].k){
        add(L[a[i].a],v[a[i].a],-1),add(R[a[i].a]+1,v[a[i].a],1);v[a[i].a]=a[i].b;
        add(L[a[i].a],v[a[i].a],1),add(R[a[i].a]+1,v[a[i].a],-1);
    }else{
        xx=a[i].a,yy=a[i].b,zz=lca(xx,yy);
        if(dep[xx]+dep[yy]-dep[zz]*2+1<a[i].k)puts("invalid request!");
        else{
            ltot=rtot=0,get(xx,1),get(yy,1),get(zz,0),get(fa[zz],0);
            printf("%d\n",y[query(a[i].k,1,cnt)]);
        }
    }
}
---By n+e
jnanabhumiap.in 说:
2024年1月19日 23:42

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic jnanabhumiap.in which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter