我也想要 hanghang 的 tag/ll/ll

给一个当前题解区没有的做法。

首先考虑哪些节点会对询问的

x

产生贡献，分成几类。

$x$ 的子树内部节点。
$x$ 的祖先。
与 $x$ 没有祖先后代关系的节点。

第一类和第三类是容易计算的。

我们考虑如何计算第二类的贡献，考虑

y

对

x

产生了贡献。

$c_y=-1$ ，此时 $x$ 在 $y$ 的子树内部即可。
$c_y=0$ ，此时需要满足 $x$ 在 $y$ 的右子树内部。

我们可以把贡献看成在边上。

考虑对于原树进行 top cluster 树分块，那么

x

到根的路径可以表示成

O(\sqrt n)

条簇路径的贡献+

O(\sqrt n)

个散点的贡献。

对于修改操作使用颜色段均摊，则我们只有

O(n+q)

次区间染色。

散点的颜色可以用

O(\sqrt n)-O(1)

的分块维护。

我们将染色操作带上

\pm 1

的贡献系数，表示染色或者删除之前的染色。

对于整块，我们需要一次染色操作带来的贡献，我们对于每个块，对于簇路径用桶维护出现节点有哪些，以及在簇路径上经过向右儿子的边的节点有哪些，对于桶做前缀和，那么我们可以

O(1)

计算出来

[l,r]

在簇路径上有多少个节点，那么我们一次染色对于一个块的影响可以

O(1)

得到，所以我们就可以在

O((n+q)\sqrt n)

的复杂度内解决，但是常数不是很小。

由于我们树分块似乎有

6\frac n B

个块，所以

B

要开大一些。

代码的块长没有调过。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,B=1.5e3,T=6*N/B+5;
int n,q,cnt1[T][N],cnt2[T][N],ch[N][2],val[N],sz[N];
int f[N],F[N],pos[N],C,sum[N];
namespace Node{
	array<int,2> t1[N],t2[N];
	int L[N],R[N],bl[N];
	inline void change(int l,int r,int t,int v){
		int p=bl[l],q=bl[r];
		if(p==q){
			for(int i=l;i<=r;++i) t1[i]={t,v};
			return;
		}
		for(int i=l;i<=R[p];++i) t1[i]={t,v};
		for(int i=p+1;i<q;++i) t2[i]={t,v};
		for(int i=L[q];i<=r;++i) t1[i]={t,v};
	}
	inline void init(){
		for(int i=1;i<=n;++i) bl[i]=(i-1)/B+1,t1[i]={0,-1};
		for(int i=1;i<=bl[n];++i) t2[i]={0,-1},L[i]=R[i-1]+1,R[i]=min(i*B,n);
	}
	inline int qry(int x){return max(t1[x],t2[bl[x]])[1];}
}
#define pii pair<int,bool>
inline pii dfs(int x,int s,int fa=0){
	if(!x) return {0,0};
	val[x]=s,f[x]=fa,sz[x]=1;
	pii t;
	int cnt=1,FL=0;
	t=dfs(ch[x][0],s,x),cnt+=t.first,FL+=t.second,s+=sz[ch[x][0]],sz[x]+=sz[ch[x][0]];
	t=dfs(ch[x][1],s,x),cnt+=t.first,FL+=t.second,sz[x]+=sz[ch[x][1]];
	if(cnt>=B||FL>1) pos[x]=++C,cnt=0;
	return {cnt,pos[x]||FL};
}
inline void dfs2(int x,int lst){
	if(!x) return;
	if(pos[x]){
		F[x]=lst,lst=x;
		for(int i=x;i!=F[x];i=f[i]){
			if(!f[i]) continue;
			++cnt1[pos[x]][f[i]];
			if(i==ch[f[i]][1]) ++cnt2[pos[x]][f[i]];
		}
		for(int i=1;i<=n;++i) cnt1[pos[x]][i]+=cnt1[pos[x]][i-1],cnt2[pos[x]][i]+=cnt2[pos[x]][i-1];
		for(int i=1;i<=n;++i) cnt1[pos[x]][i]+=cnt1[pos[F[x]]][i],cnt2[pos[x]][i]+=cnt2[pos[F[x]]][i];
	}
	dfs2(ch[x][0],lst),dfs2(ch[x][1],lst);
}
struct node{
	int l,r,c;
	inline node(int _l=0,int _r=0,int _x=0){l=_l,r=_r,c=_x;}
	inline bool operator <(const node a)const{return l<a.l;}
};
set<node>S;
#define Iter set<node>::iterator
inline Iter split(int x){
	Iter it=S.lower_bound(node(x));
	if(it!=S.end()&&it->l==x) return it;
	--it;
	int c=it->c,L=it->l,R=it->r;
	S.erase(it),S.insert(node(L,x-1,c));
	return S.insert(node(x,R,c)).first;
}
inline void change(int l,int r,int x){
	Iter ed=split(r+1),st=split(l);
	S.erase(st,ed),S.insert(node(l,r,x));
}
inline void mdf(int L,int R,int x,int v){
	if(x==-1) for(int i=2;i<=C;++i) sum[i]+=(cnt1[i][R]-cnt1[i][L-1])*v;
	if(x==0) for(int i=2;i<=C;++i) sum[i]+=(cnt2[i][R]-cnt2[i][L-1])*v;
}
inline void assign(int l,int r,int x,int t){
	auto ed=split(r+1),st=split(l);
	for(auto it=st;it!=ed;++it) mdf(it->l,it->r,it->c,-1);
	S.erase(st,ed),S.insert(node(l,r,x)),mdf(l,r,x,1),Node::change(l,r,t,x);
}
inline int calc(int x){
	int ans=1+val[x],c=Node::qry(x);
	if(c==0) ans+=sz[ch[x][0]];
	if(c==1) ans+=sz[ch[x][0]]+sz[ch[x][1]];
	while(!pos[x]){
		if(!f[x]) return ans;
		if((c=Node::qry(f[x]))==-1) ++ans;
		else if(c==0&&x==ch[f[x]][1]) ++ans;
		x=f[x];
	}
	return ans+sum[pos[x]];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q,pos[0]=C=1;
	for(int i=1;i<=n;++i) cin>>ch[i][0]>>ch[i][1];
	dfs(1,0),dfs2(1,0),S.insert(node(1,n+1,-1)),mdf(1,n,-1,1),Node::init();
	for(int opt,l,r,x,i=1;i<=q;++i){
		cin>>opt;
		if(opt==1) cin>>l>>r>>x,assign(l,r,x,i);
		else cin>>x,cout<<calc(x)<<"\n";
	}
}

我也想要 hanghang 的 tag/ll/ll

文章操作

相关推荐

评论

我也想要 hanghang 的 tag/ll/ll