自动搬运

查看原文

来自洛谷，原作者为

	Spectator 我趁有半天空档 ／ 为你跑一趟 ／ 城市里永远有宝藏

搬运于2025-08-24 23:06:16，当前版本为作者最后更新于2024-11-25 20:33:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的食用体验 $|$ 题目传送门 $|$ 我的其他题解

% 你赛题，水篇题解（逃

${\color{#00CD00}\text{思路}}$

两条性质：

• 一棵二叉树是 BST 当且仅当这棵树的中序遍历是单调不降的。
• 一个子树的中序遍历是整颗树的中序遍历中连续的一段。

先跑一遍 dfs，求出整颗树的中序遍历，同时记录下每个结点的子树的中序遍历在整颗树的中序遍历中的位置。这样判断一个子树是否是 BST 就只需要用树状数组维护对应的区间内不满足 $a_i \le a_{i+1}$ 的数量。

考虑如何修改。发现每次修改只会影响这个结点到根结点的路径。树上倍增更新答案即可。

时间复杂度为 $O(n\log^2n)$。实现细节见代码。

${\color{#00CD00}\text{代码}}$

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=a; i<=b; i++)
using namespace std;
const int N = 2e5 + 5;
long long n, q, ans;
int a[N], f[N][20];
int dfn;
struct Node{
	int ls, rs, val;
	int pos, l, r;
}t[N];
void dfs(int _u){
	if(!_u) return;
	Node &u = t[_u];
	u.l = dfn + 1, dfs(u.ls);
	u.pos = ++dfn, a[u.pos] = u.val;
	dfs(u.rs), u.r = dfn;
}
struct BIT{
	int c[N], lowbit(int x){return x & -x;}
	void update(int x, int k){while(x <= n) c[x] += k, x += lowbit(x);}
	int query(int x){int s = 0; while(x) s += c[x], x -= lowbit(x); return s;}
}bit;
void upd(int k, int x){
	if(k < n && a[k] > a[k+1]) bit.update(k, x);
	if(k > 1 && a[k-1] > a[k]) bit.update(k-1, x);
}
bool check(int x){
	return bit.query(t[x].r-1) - bit.query(t[x].l-1) == 0;
}
int solve(int x){
	if(!check(x)) return 0;
	int res = 1;
	for(int i=19; i>=0; i--){
		if(f[x][i] && check(f[x][i])){
			x = f[x][i], res += 1 << i;
		}
	}
	return res;
}
signed main(){
	cin.tie(nullptr) -> sync_with_stdio(false);
	cin >> n >> q;
	rep(i, 1, n){
		cin >> t[i].ls >> t[i].rs;
		if(t[i].ls) f[t[i].ls][0] = i;
		if(t[i].rs) f[t[i].rs][0] = i;
	}
	rep(i, 1, n) cin >> t[i].val;
	rep(j, 1, 19) rep(i, 1, n) f[i][j] = f[f[i][j-1]][j-1];
	dfs(1);
	rep(i, 1, n-1) bit.update(i, a[i] > a[i+1]);
	rep(i, 1, n) if(check(i)) ans++;
	while(q --> 0){
		int k, x; cin >> k >> x;
		ans -= solve(k);
		upd(t[k].pos, -1);
		a[t[k].pos] = x;
		upd(t[k].pos, 1);
		ans += solve(k);
		cout << ans << "\n";
	}
	return 0;
}