传送门-->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(n\log^2 n)$
#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 100010
int 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)
