BZOJ-1146 [CTSC2008]网络管理Network
以前看到这题以为不可写,树链剖分+线段树套平衡树,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)]); } } }