传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3637
我居然作死点了这道题
显然可以lct硬上，但是突然就不想写lct，没办法用树剖将就一下
显然可以只存子树的答案，询问的时候只要找到最高那个点就行了，记黑点为1，白点为0，因为要是连续的，所以连续一段1一定是这些点的个数，0的话一定是0，于是这个东西是单调的，树剖之后往上爬，不能爬了就在这条重链里二分即可，发现是单点修改和区间查询，用一个树状数组就好了
然后就是要维护答案，我想不出直接维护的方法，把一棵树分成两棵，一棵专门搞黑的，另一棵白的，修改的时候，设修改的点为x，则要修改的链是x的父亲到这个同色块最上面的点u的父亲，为什么还要修改u的父亲？因为之后当u变色时就能方便的继承从儿子传来的贡献了，所以一次操作同时修改两棵树
感觉很优美，发现只有区间修改和单点询问，于是就再用两个树状数组，一共3个
刚开始狂T不止，还以为树状数组都被卡常了，网上有题解是每条重链一棵线段树，好神呀，不过还好数据没有第二天才到，只是有细节写错导致死循环了，有兴趣的同学可以每条重链一个树状数组刷rank，2333，应该比线段树快到不知道哪里去了
复杂度：O(nlog2n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include<cstring>#include<cstdio>#include<algorithm>using namespace std;#define nc() getchar()inline int read(){ int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc()); for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;}#define N 100010int i,j,f,k,m,n,x,y,t1[N],t2[N],t3[N],cnt,last[N],top[N],id[N],dep[N],sz[N],fa[N],son[N],now,a[N],rk[N];struct edge{int to,next;}e[N<<1];void dfs1(int x,int d){ sz[x]=1,dep[x]=d; for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]){ fa[y]=x,dfs1(y,d+1),sz[x]+=sz[y]; if(sz[y]>sz[son[x]])son[x]=y; }}void dfs2(int x,int d){ top[x]=d,rk[id[x]=++now]=x;if(son[x])dfs2(son[x],d); for(int i=last[x],y;i;i=e[i].next)if((y=e[i].to)!=fa[x]&&y!=son[x])dfs2(y,y);}inline void add(int u,int v){ e[++cnt]=(edge){v,last[u]},last[u]=cnt; e[++cnt]=(edge){u,last[v]},last[v]=cnt;}inline void t2_add(int x,int d){for(;x<=n;x+=x&-x)t2[x]+=d;}inline void t1_add(int x,int d){for(;x<=n;x+=x&-x)t1[x]+=d;}inline void t3_add(int x,int d){for(;x<=n;x+=x&-x)t3[x]+=d;}inline int t1_ask(int x){int ret=0;for(;x;x-=x&-x)ret+=t1[x];return ret;}inline int t2_ask(int x){int ret=0;for(;x;x-=x&-x)ret+=t2[x];return ret;}inline int t3_ask(int x){int ret=0;for(;x;x-=x&-x)ret+=t3[x];return ret;}inline int ef(int l,int r,int col){ for(int m=l+r>>1;l<=r;m=l+r>>1)(col?(t2_ask(r)-t2_ask(m-1)==r-m+1):(t2_ask(r)-t2_ask(m-1)==0))?r=m-1:l=m+1; return rk[r+1];}inline int up(int x,int col){ while(top[x]!=1)if(col)if(id[x]-id[top[x]]+1==t2_ask(id[x])-t2_ask(id[top[x]]-1)) if(a[fa[top[x]]])x=fa[top[x]];else return top[x];else return ef(id[top[x]],id[x],col); else if(t2_ask(id[x])-t2_ask(id[top[x]]-1))return ef(id[top[x]],id[x],col); else if(a[fa[top[x]]])return top[x];else x=fa[top[x]]; return ef(1,id[x],col);}inline void change(int x,int y,int v,int col){ if(dep[x]<dep[y])return; for(;top[x]!=top[y];x=fa[top[x]])col?(t1_add(id[top[x]],v),t1_add(id[x]+1,-v)):(t3_add(id[top[x]],v),t3_add(id[x]+1,-v)); col?(t1_add(id[y],v),t1_add(id[x]+1,-v)):(t3_add(id[y],v),t3_add(id[x]+1,-v));}int main(){ for(n=read(),i=1;i<n;++i)add(read(),read()); for(dfs1(1,1),dfs2(1,1),i=1;i<=n;++i)t2_add(i,a[i]=1); for(t3_add(1,1),i=1;i<=n;++i)t1_add(i,sz[rk[i]]),t1_add(i+1,-sz[rk[i]]); for(m=read();m--;){ f=read(),x=read(); if(f)a[x]?(change(fa[x],max(1,fa[up(x,a[x])]),-t1_ask(id[x]),1), t2_add(id[x],-1),change(fa[x],max(1,fa[up(x,a[x]=0)]),t3_ask(id[x]),0)): (change(fa[x],max(1,fa[up(x,a[x])]),-t3_ask(id[x]),0), t2_add(id[x],1),change(fa[x],max(1,fa[up(x,a[x]=1)]),t1_ask(id[x]),1)); else printf("%d\n",a[x]?t1_ask(id[up(x,a[x])]):t3_ask(id[up(x,a[x])])); }} |
loading...
评论 (0)
