题解：P14380 【MX-S9-T3】「LAOI-16」天外来物

· · 题解

不错的数据结构题。

一个比较自然的想法是，你考虑把所有同一种“天外来物”都在一个最小的区间里计算贡献。换句话说，我们会计算 [l,r] 的贡献，当且仅当 f(l,r) \ne f(l+1,r) 且 f(l,r) \ne f(l,r-1)。我们称这种 [l,r] 为“极小区间”。

那一段区间内所有不同“天外来物”的个数其实就是所有上述“极小区间”被完全包含的个数。通过二维差分前缀和可以做到 O(n^2+q)。

考虑优化这个过程。

你发现实际上，这个东西是具有某种“单调性”的。具体的，对于一个左端点 l，存在一个位置 nxt_l，这这之后所有的 [l,r] 都不可能是“极小区间”。

考虑探求一下这个 nxt 的本质。其实一个极小区间，相当于是 l 和 r 这两个点都在这个“天外来物”的叶子上。nxt 的含义，其实就是从一个位置开始，这个 l 不可能再成为叶子。

先考虑怎么求这个 nxt_l。你发现，因为它不是叶子，所以它的度数至少为 2，也就是会向两个方向分叉。因此，实际上就是与它相连的，所有，子树中大于 l 的最小值，的次小值。

有点难说，还是上柿子吧。定义 \operatorname{smin}(i,j,k,\dots) 表示这些数的次小值。定义 dir_l 表示与 l 所连的所有点构成的集合，定义 rt_{u,v} 表示以 u 为根的情况下 v 的子树中所有节点构成的集合。那么有：

nxt_l = \operatorname{smin}_{v \in dir_l} \left( \min_{d \in rt_{l,v},d > l} d \right) - 1

这个可以把树拍到 dfn 序上，然后扫描线，按 l 从大到小做即可。

我们类似定义 pre_r 表示从一个位置开始，右端点 r 不可能再成为叶子。

那么一个区间 [l,r] 是极小区间的充要条件其实就是：

pre_r \le l \le r \le nxt_l

这个看上去就比较可以扫描线了。

你发现其实就相当于，你要对于所有的 nxt_l 大于等于当前 r 的 l 贡献加一。这个线段树简单维护即可。定义 l“被激活”表示 nxt_l \ge r，线段树上记录当前区间有多少个被激活的点即可。

然后查询就挂到右端点上区间查 [l,r] 即可。

AC Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
using namespace std ;
const int MAXN = 5e5 + 7 ;
const int INF = 1e9 + 7 ;
vector<int> dir[MAXN] ;

int dep[MAXN] , fa[MAXN] , dfn[MAXN] , sz[MAXN] , lst ;
void dfs(int u , int f , int d) {
    fa[u] = f ;
    dep[u] = d ;
    dfn[u] = ++lst ;
    sz[u] = 1 ;

    for (auto v : dir[u]) {
        if (v == f) continue ;
        dfs(v , u , d + 1) ;
        sz[u] += sz[v] ;
    }
}

struct SegmentTree1 {
    int tr[4 * MAXN] ;

    void BuildTree(int u , int l , int r) {
        tr[u] = -INF ;
        if (l == r) return ;

        int mid = (l + r) >> 1 ;
        BuildTree(u * 2 , l , mid) ;
        BuildTree(u * 2 + 1 , mid + 1 , r) ;
        return ;
    }

    void Change(int u , int l , int r , int dir , int val) {
        if (l == r) {
            tr[u] = val ;
            return ;
        }

        int mid = (l + r) >> 1 ;
        if (mid >= dir) Change(u * 2 , l , mid , dir , val) ;
        else    Change(u * 2 + 1 , mid + 1 , r , dir , val) ;
        tr[u] = max(tr[u * 2] , tr[u * 2 + 1]) ;
    }

    int Query(int u , int l , int r , int gl , int gr) {
        if (gl > gr)    return -INF ;

        if (gl <= l and r <= gr) {
            return tr[u] ;
        }

        int mid = (l + r) >> 1 ;
        int ans = -INF ;
        if (mid >= gl)  ans = max(ans , Query(u * 2 , l , mid , gl , gr)) ;
        if (mid + 1 <= gr)  ans = max(ans , Query(u * 2 + 1 , mid + 1 , r , gl , gr)) ;

        return ans ;
    }
}o ;

int pre[MAXN] , nxt[MAXN] ;

struct SegmentTree2 {
    ll cnt[4 * MAXN] ;
    ll sum[4 * MAXN] ;
    ll lan[4 * MAXN] ;

    void push_up(int u) {
        cnt[u] = cnt[u * 2] + cnt[u * 2 + 1] ;
        sum[u] = sum[u * 2] + sum[u * 2 + 1] ;
    }

    void BuildTree(int u , int l , int r) {
        if (l == r) {
            cnt[u] = 1 ;
            sum[u] = 0 ;
            lan[u] = 0 ;
            return ;
        }

        int mid = (l + r) >> 1 ;
        BuildTree(u * 2 , l , mid) ;
        BuildTree(u * 2 + 1 , mid + 1 , r) ;
        push_up(u) ; 
    }

    void push_down(int u) {
        if (!lan[u])    return ;

        sum[u * 2] += cnt[u * 2] * lan[u] ;
        sum[u * 2 + 1] += cnt[u * 2 + 1] * lan[u] ;
        lan[u * 2] += lan[u] ;
        lan[u * 2 + 1] += lan[u] ;

        lan[u] = 0 ;
        return ;
    }

    void Add(int u , int l , int r , int gl , int gr) {
        if (gl <= l and r <= gr) {
            sum[u] += cnt[u] ;
            lan[u] ++ ;
            return ;
        }

        push_down(u) ;

        int mid = (l + r) >> 1 ;
        if (mid >= gl)  Add(u * 2 , l , mid , gl , gr) ;
        if (mid + 1 <= gr)  Add(u * 2 + 1 , mid + 1 , r , gl , gr) ;

        push_up(u) ;
        return ;
    }

    void Modify(int u , int l , int r , int dir) {
        if (l == r) {
            cnt[u] = 0 ;
            return ;
        }

        push_down(u) ;
        int mid = (l + r) >> 1 ;
        if (mid >= dir) Modify(u * 2 , l , mid , dir) ;
        else    Modify(u * 2 + 1 , mid + 1 , r , dir) ;

        push_up(u) ;
    }

    ll Query(int u , int l , int r , int gl , int gr) {
        if (gl <= l and r <= gr) {
            return sum[u] ; 
        }

        ll ans = 0 ;
        push_down(u) ;
        int mid = (l + r) >> 1 ;
        if (mid >= gl)  ans += Query(u * 2 , l , mid , gl , gr) ;
        if (mid + 1 <= gr)  ans += Query(u * 2 + 1 , mid + 1 , r , gl , gr) ;

        return ans ;
    }
}p ;

struct Ques {
    int l ;
    int u ;
};

vector<Ques> g[MAXN] ;
ll ans[MAXN] ;
vector<int> del[MAXN] ;

signed main() {
    freopen("tree.in" , "r" , stdin) ;
    freopen("tree.out" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int c , n , q ;
    cin >> c >> n >> q ;

    for (int i = 1 ; i < n ; i ++) {
        int u , v ;
        cin >> u >> v ;
        dir[u].push_back(v) ;
        dir[v].push_back(u) ;
    }

    dfs(1 , 0 , 1) ;

    o.BuildTree(1 , 1 , n) ;
    for (int i = 1 ; i <= n ; i ++) {
        int mx = -INF , smx = -INF ;

        for (auto v : dir[i]) {
            if (v == fa[i]) continue ;

            int val = o.Query(1 , 1 , n , dfn[v] , dfn[v] + sz[v] - 1) ;
            if (val > mx) {
                smx = mx ;
                mx = val ;
            }
            else if (val > smx) {
                smx = val ;
            }
        }

        if (i != 1) {
            int val = max(o.Query(1 , 1 , n , 1 , dfn[i] - 1) , o.Query(1 , 1 , n , dfn[i] + sz[i] , n)) ;
            if (val > mx) {
                smx = mx ;
                mx = val ;
            }
            else if (val > smx) {
                smx = val ;
            }
        }

        if (smx == -INF) {
            pre[i] = 1 ;
        }
        else {
            pre[i] = smx + 1 ;
        }

        o.Change(1 , 1 , n , dfn[i] , i) ;
    }

    o.BuildTree(1 , 1 , n) ;
    for (int i = n ; i >= 1 ; i --) {
        int mx = -INF , smx = -INF ;

        for (auto v : dir[i]) {
            if (v == fa[i]) continue ;

            int val = o.Query(1 , 1 , n , dfn[v] , dfn[v] + sz[v] - 1) ;
            if (val > mx) {
                smx = mx ;
                mx = val ;
            }
            else if (val > smx) {
                smx = val ;
            }
        }

        if (i != 1) {
            int val = max(o.Query(1 , 1 , n , 1 , dfn[i] - 1) , o.Query(1 , 1 , n , dfn[i] + sz[i] , n)) ;
            if (val > mx) {
                smx = mx ;
                mx = val ;
            }
            else if (val > smx) {
                smx = val ;
            }
        }

        if (smx == -INF) {
            nxt[i] = n ;
        }
        else {
            nxt[i] = -smx - 1 ;
        }

        o.Change(1 , 1 , n , dfn[i] , -i) ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        del[nxt[i]].push_back(i) ;
    }

    for (int i = 1 ; i <= q ; i ++) {
        int l , r ;
        cin >> l >> r ;
        g[r].push_back({l , i}) ;
    }

    p.BuildTree(1 , 1 , n) ;
    for (int i = 1 ; i <= n ; i ++) {
        p.Add(1 , 1 , n , pre[i] , i) ;

        for (auto e : g[i]) {
            ans[e.u] = p.Query(1 , 1 , n , e.l , i) ;
        }

        for (auto e : del[i]) {
            p.Modify(1 , 1 , n , e) ;
        }
    }

    for (int i = 1 ; i <= q ; i ++) {
        cout << ans[i] << "\n" ;
    }

    return 0 ;
}