P11306 [COTS 2016] 搜索树 Jelka 题解

_Spectator_ · 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;
}