天外来物

Mier_Samuelle · 2026-11-11 11:46:58 · 题解

称区间 [l,r] 极小，当且仅当 f(l-1,r) \ne f(l,r) 且 f(l,r-1) \ne f(l,r)。这等价于 l,r 均为 f(l,r) 的叶子。对于询问 [L,R]，我们要求的就是满足 L \le l \le r \le R 的极小区间 [l,r] 的个数。

当 l 固定时，「l 是否是 f(l,r) 的叶子」对 r 具有单调性。具体而言，可以找到 \text{nxt}_l，使得对于任意 r \in [l,\text{nxt}_l]，l 是 f(l,r) 的叶子，且对于任意 r \in (\text{nxt}_l,n]，l 不是 f(l,r) 的叶子。同理可以定义 \text{prv}_r。这样区间 [l,r] 极小的充要条件就可以被刻画为 \text{prv}_r \le l \le r \le \text{nxt}_l。

先考虑怎么求 \text{prv} 和 \text{nxt}。这里以 \text{nxt} 为例。l 不是叶子，相当于钦定 l 为树的根后，有至少两棵子树内包含编号 >l 的节点。也就是说，记 \text{mn}_u 为 u 的子树中编号 >l 的节点的最小编号，\text{nxt}_l 就等于所有子树的 \text{mn} 值的次小值减一。要求这个东西，首先倒序枚举 l，每次查询的要么是一段连续的 dfn 序，要么是两段 dfn 序拼起来，上线段树维护即可。

然后考虑怎么回答询问。倒序扫描 l，将询问挂在左端点上。每次将区间 [l,\text{nxt}_l] 加一，并在 \text{prv}_r 处撤销 r 的所有贡献，询问的答案就是 [L,R] 的区间和。

复杂度 O(n \log n+q \log n)。

:::success[Code]{open}

#include <bits/stdc++.h>
#define lc (u << 1)
#define rc ((u << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;
vector <int> adj[MAXN], del[MAXN];
vector <pair<int, int>> idx[MAXN];
int dfn[MAXN], siz[MAXN], fa[MAXN], nxt[MAXN], prv[MAXN], n, q, cur;
ll ans[MAXN];
void dfs(int u, int p){
    dfn[u] = ++cur;
    siz[u] = 1;
    fa[u] = p;
    for (int v : adj[u]){
        if (v == p){
            continue;
        }
        dfs(v, u);
        siz[u] += siz[v];
    }
    return;
}
struct Segment_tree1{
    int mn[MAXN * 4];
    void pushup(int u){
        mn[u] = min(mn[lc], mn[rc]);
        return;
    }
    void build(int u, int l, int r){
        mn[u] = INF;
        if (l == r){
            return;
        }
        build(lc, l, mid);
        build(rc, mid + 1, r);
        return;
    }
    void modify(int u, int l, int r, int pos, int x){
        if (l == r){
            mn[u] = x;
            return;
        }
        if (pos <= mid){
            modify(lc, l, mid, pos, x);
        }
        else{
            modify(rc, mid + 1, r, pos, x);
        }
        pushup(u);
        return;
    }
    int query(int u, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr){
            return mn[u];
        }
        int res = INF;
        if (ql <= mid){
            res = min(res, query(lc, l, mid, ql, qr));
        }
        if (qr > mid){
            res = min(res, query(rc, mid + 1, r, ql, qr));
        }
        return res;
    }
}tr1;
struct Segment_tree2{
    ll sum[MAXN * 4], tag[MAXN * 4];
    int cnt[MAXN * 4];
    void pushup(int u){
        sum[u] = sum[lc] + sum[rc];
        cnt[u] = cnt[lc] + cnt[rc];
        return;
    }
    void pushdown(int u, int l, int r){
        if (tag[u]){
            sum[lc] += 1LL * cnt[lc] * tag[u];
            sum[rc] += 1LL * cnt[rc] * tag[u];
            tag[lc] += tag[u];
            tag[rc] += tag[u];
            tag[u] = 0;
        }
        return;
    }
    void modify(int u, int l, int r, int ql, int qr, ll x){
        if (ql <= l && r <= qr){
            sum[u] += 1LL * cnt[u] * x; 
            tag[u] += x;
            return;
        }
        pushdown(u, l, r);
        if (ql <= mid){
            modify(lc, l, mid, ql, qr, x);
        }
        if (qr > mid){
            modify(rc, mid + 1, r, ql, qr, x);
        }
        pushup(u);
        return;
    }
    void assign(int u, int l, int r, int pos, int val){
        if (l == r){
            cnt[u] = val;
            return;
        }
        pushdown(u, l, r);
        if (pos <= mid){
            assign(lc, l, mid, pos, val);
        }
        else{
            assign(rc, mid + 1, r, pos, val);
        }
        pushup(u);
        return;
    }
    ll query(int u, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr){
            return sum[u];
        }
        pushdown(u, l, r);
        ll res = 0;
        if (ql <= mid){
            res += query(lc, l, mid, ql, qr);
        }
        if (qr > mid){
            res += query(rc, mid + 1, r, ql, qr);
        }
        return res;
    }
}tr2;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    tr1.build(1, 1, n);
    for (int i = n; i >= 1; i--){
        int mn1 = INF, mn2 = INF;
        for (int u : adj[i]){
            int val = 0;
            if (fa[i] == u){
                val = min(tr1.query(1, 1, n, 1, dfn[i] - 1), tr1.query(1, 1, n, dfn[i] + siz[i], n));
            }
            else{
                val = tr1.query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
            }
            if (val < mn1){
                mn2 = mn1;
                mn1 = val;
            }
            else if (val < mn2){
                mn2 = val;
            }
        }
        nxt[i] = mn2 - 1;
        tr1.modify(1, 1, n, dfn[i], i);
    }
    tr1.build(1, 1, n);
    for (int i = 1; i <= n; i++){
        int mx1 = -INF, mx2 = -INF;
        for (int u : adj[i]){
            int val = 0;
            if (fa[i] == u){
                val = -min(tr1.query(1, 1, n, 1, dfn[i] - 1), tr1.query(1, 1, n, dfn[i] + siz[i], n));
            }
            else{
                val = -tr1.query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1);
            }
            if (val > mx1){
                mx2 = mx1;
                mx1 = val;
            }
            else if (val > mx2){
                mx2 = val;
            }
        }
        prv[i] = mx2 + 1;
        tr1.modify(1, 1, n, dfn[i], -i);
        if (prv[i] < 0){
            prv[i] = 1;
        }
        del[prv[i]].push_back(i);
    }
    for (int i = 1; i <= q; i++){
        int l, r;
        cin >> l >> r;
        idx[l].push_back({r, i});
    }
    for (int i = n; i >= 1; i--){
        tr2.assign(1, 1, n, i, 1);
        tr2.modify(1, 1, n, i, nxt[i], 1);
        for (auto [r, id] : idx[i]){
            ans[id] = tr2.query(1, 1, n, i, r);
        }
        for (int r : del[i]){
            tr2.assign(1, 1, n, r, 0);
        }
    }
    for (int i = 1; i <= q; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

:::