4
18
2016
0

[bzoj]3637: Query on a tree VI

传送门-->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...$

Category: bzoj | Tags: 树状数组 线段树 LCT 树剖 | Read Count: 1012

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com