P11127 [ROIR 2024 Day 2] 二叉树的遍历

Des

一棵树，两种操作：

• 1 l r type 表示将 $[l,r]$ 的节点所在的子树的遍历顺序改为 type。
• 2 x 表示查询当前遍历顺序之下，$x$ 在遍历序列中的位置。

其中 type 表示：

• type = -1 时，该子树前序遍历。
• type = 0 时，该子树中序遍历。
• type = 1 时，该子树后序遍历。

Sol

这个玩意看起来就极其不可用兼容性不高的数据结构做，而且 $n,q\le 10^5$，因此我们使用分块。

首先，我们要考虑什么样的点能够在 $x$ 前面。

• $x$ 子树为中序遍历，$y$ 在 $x$ 的左子树。
• $x$ 子树为后序遍历，$y$ 在 $x$ 的子树内。
• 存在一个 $z$ 使得 $x$ 在 $z$ 的右子树而 $y$ 在 $x$ 的左子树。
• $y$ 为前序遍历，$x$ 在它的子树内。
• $y$ 为中序遍历，$x$ 在它的右子树内。

一共就这么 $5$ 种情况。对于前三种，我们是可以根据当时 $x$ 的类型直接判断出来，因此我们只需要考虑前两种。

• 首先，我们考虑如果一个块内，所有的点的遍历类型都相同，那么显然我们可以提前处理出来它们的贡献。

  具体的，我们设 $g_{0/1,i,j}$ 表示 type = -1/0 时，$i$ 对 $dfn_x=j$ 的 $x$ 的贡献。这里 $0/1$ 是因为在 type = 1，也就是后序遍历的时候，$i$ 不产生贡献。而当 type = -1，也就是前序遍历的时候，它会对子树全部加一，type = 0 也就是中序遍历的时候，它会对右子树全部加一。都是子树加，因此使用 dfn 显然会更加方便。

• 其次，我们考虑散块的贡献。

  细想一下就会发现，散块的计算是非常困难的，因此我们干脆暴力计算。

  但时间复杂度怎么保证呢？

  考虑一次修改至多会产生两个散块，而每个散块重构的复杂度为 $O(\sqrt n)$，因此复杂度为完全可以接受。

  在把一个整块全部变成散块的时候，我们更改块内标记，然后暴力地将每个点的贡献都算上。注意这里需要一个 $O(1)-O(\sqrt n)$，也就是询问 $O(\sqrt n)$ 修改 $O(1)$ 的分块来平衡复杂度，而不是傻乎乎地去写树状数组。然后，在把散块都暴力整合成整块的时候，我们就把它们在散块上的贡献都清除掉即可。

另外，还有一点需要注意：在处理第 $1,2$ 条产生的贡献的时候，我们需要用到 $x$ 具体是哪个遍历类型，而这时候我们不能直接使用 type[x] 来获取，而是需要判断它所处的块是不是散块，如果不是则以块的类型为准。

#define endl '\n'
using namespace std;
const int N = 1e5 + 10;
const int B = 300;
const int T = N/B + 5;	
inline int min(int x,int y){ return x < y ? x : y; }
inline int max(int x,int y){ return x < y ? y : x; }

int n, q, ch[N][2];
int ga[T][N], gr[T][N], m[N], mb[N];
int bef[N], mid[N], aft[N], idx, siz[N];
int bl[N], le[N], ri[N], type[N], btype[N];

void dfs(int x){
	if(!x)	return ;
	bef[x] = ++idx; dfs(ch[x][0]); mid[x] = idx; dfs(ch[x][1]); aft[x] = idx;
	siz[x] += siz[ch[x][0]] + siz[ch[x][1]] + 1;
}

inline void add(int x,int k){ m[x] += k, mb[bl[x]] += k;}
inline void add(int l,int r,int k){ add(l, k), add(r+1, -k); }
inline void update(int x,int k){
	if(type[x] == -1)	add(bef[x] + 1, aft[x], k);
	if(type[x] == 0)	add(mid[x] + 1, aft[x], k);
}
inline void _modify(int l,int r,int k){
	int block = bl[l];
	if(btype[block] == 2){
		for(int i=l;i<=r;++i)	update(i, -1), type[i] = k, update(i, 1);
	}else{
		for(int i = le[block]; i <= ri[block]; ++i)	type[i] = btype[block];
		for(int i = l; i <= r; ++i)	type[i] = k;
		for(int i = le[block]; i <= ri[block]; ++i)	update(i, 1);
		btype[block] = 2;
	}
}
inline void modify(int l,int r,int k){
	if(bl[l] == bl[r])	return _modify(l, r, k);
	_modify(l, ri[bl[l]], k), _modify(le[bl[r]], r, k);
	for(int i = bl[l]+1; i < bl[r]; ++i){
		if(btype[i] == 2)	for(int j = le[i]; j <= ri[i]; ++j)	update(j, -1);
		btype[i] = k;
	}
}
inline int solve(int x){
	int ans = 1;
	for(int i=1;i<bl[bef[x]];++i)	ans += mb[i];
	for(int i=le[bl[bef[x]]];i<=bef[x];++i)	ans += m[i];
	int k = btype[bl[x]] == 2 ? type[x] : btype[bl[x]];
	if(k == 0)	ans += siz[ch[x][0]];
	if(k == 1)	ans += siz[x] - 1;
	for(int i=1;i<=bl[n];++i){
		if(btype[i] == -1)	ans += ga[i][bef[x]];
		if(btype[i] == 0)	ans += gr[i][bef[x]];
	}
	return ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i)	cin>>ch[i][0]>>ch[i][1], type[i] = -1;
	for(int i=1;i<=n;++i)	bl[i] = (i-1)/B+1, type[i] = -1;
	for(int i=1;i<=bl[n];++i)	btype[i] = 2, le[i] = ri[i-1] + 1, ri[i] = min(i * B, n);
	dfs(1);
	for(int i=1;i<=n;++i){
		update(i, 1);
		add(mid[i]+1, aft[i], siz[ch[i][0]]);
		ga[bl[i]][bef[i]+1] ++, ga[bl[i]][aft[i]+1] --;
		gr[bl[i]][mid[i]+1] ++, gr[bl[i]][aft[i]+1] --;
	}
	for(int i=1;i<=bl[n];++i)
		for(int j=1;j<=n;++j)	ga[i][j] += ga[i][j-1], gr[i][j] += gr[i][j-1];
	while(q--){
		int op, l, r, x; cin>>op;
		if(op == 1)	cin>>l>>r>>x, modify(l, r, x);
		else	cin>>x, cout<<solve(x)<<endl;
	}
	return 0;
}