题解：P10302 [THUWC 2020] 某科学的动态仙人掌

liujiaxi123456 · 2025-01-13 21:45:08 · 题解

\@代表元思想

思路：

先概括一下模型：满足某种条件的区间极大连通块计数。

*极大 = 划分 -> 标志物（把一个序列划分到标志物的左/右等） -> 最高点。

由于一个点只能唯一属于一个极大连通块，所以考虑通过统计最高点以统计连通块。

由于 dep 可能有相同的，于是用 bfn 比较。

模型转化完毕，把条件重新总结一下：

对于一个 u \in [l, r] ，若不存在一个满足以下条件的 v，则 u 是 [l, r] 的一个答案：
- v\in[l, r]
- dis(v, u)\le k
- bfn_v < bfn_u

显然考虑预处理 + 查询，观察到 [l, r] 的后效性不强（指 l,r 都没有参与剩下条件的运算），于是考虑一个小 Trick：

可以预处理出 L_u, R_u 表示满足剩余条件时 l,r 最多能取到哪里。

然后查询：

ans = \sum_{u=l}^r [L_u\le l]\cdot [r\le R_u]
三维偏序，使用容斥优化。
ans = (r-l+1) - \sum_{u=l}^r [l<L_u] - \sum_{u=l}^r [R_u<r] + \sum_{u=l}^r [l<L_u]\cdot [R_u<r]
发现最后那个 u 的范围可以扩展到 [1, n] ，所以实际上是二维偏序，如下：
ans = (r-l+1) - \sum_{u=l}^r [l<L_u] - \sum_{u=l}^r [R_u<r] + \sum_{u=1}^n [l<L_u]\cdot [R_u<r]
二维偏序，直接树状数组即可。

考虑预处理：

求 L_u, R_u 相当于求离 u 最近的满足上述条件后两个条件的元素。
由于限制中有与距离相关的邻域信息，考虑使用点分治/点分树维护。
对于限制 dis(v, u) \le k ：
- 在每个点分祖先处维护一个以元素编号为下标的线段树。
- 查询时枚举每个点分祖先后在线段树上二分即可。
对于另一限制 bfn_v < bfn_u ：
- 发现我们只要保证目前线段树里的元素的 bfn 都 < bfn_u 即可。
- 于是考虑在预处理扫描线时按照 bfn 的顺序即可。

优化/卡常：

空间：
- 显然现在的空间复杂度是 O(n\log^2 n) 的，不能通过。
- 我们现在是对每个元素去遍历它的点分祖先，由于所有祖先都要存下来，很浪费空间。
- 考虑正难则反，对于每个点分祖先，去给它的所有点分子树提供贡献。
- 这样每次就只用一棵线段树，是 O(n) 的。
时间：
- 线段树可以写非递归。
- 点分治在遍历当前点分祖先所管辖的元素时，在 dep_u > K 后就可以不遍历后面的子树了，直接 return。
- 如果当前的 L_u/R_u 已经等于 u-1/u+1 了，就不用再更新了。

Code：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn = 3e5+5, Maxq = 6e5+5;

namespace EDGE {
    int sz, head[Maxn];
    struct Edge { int next, to; } edge[Maxn*2];
    inline void Add_edge(int u, int v) {
        edge[++sz] = {head[u], v};
        head[u] = sz;
    }
} using namespace EDGE;

class SegmentTree {
private:
    const int INF = INT_MAX/2-5; int cnt, rt, limit;
    struct Segment { int ls, rs, mn; } seg[Maxn<<2];
    inline void newnode(int &t) {
        t = ++cnt, seg[t].ls = seg[t].rs = 0, seg[t].mn = INF;
    }
    inline int Queryl(int t, int l, int r, int L, int R, int val) {
        if(!t || r<L || R<l || (seg[t].mn > val))   return 0;
        if(L<=l and r<=R) {
            for(int mid; l^r; ) {
                // printf("t:%d, l:%d, r:%d, mn:%d, val:%d\n", t, l, r, seg[t].mn, val);
                mid = (l+r)>>1;
                if(seg[t].rs and seg[seg[t].rs].mn <= val)  t = seg[t].rs, l = mid+1;
                else    t = seg[t].ls, r = mid;
            }
            // printf("l:%d, r:%d, t:%d\n", l, r, t);
            return l;
        }
        int mid = (l+r)>>1;
        int res = Queryl(seg[t].rs, mid+1, r, L, R, val);
        return res ?res :Queryl(seg[t].ls, l, mid, L, R, val);
    }
    inline int Queryr(int t, int l, int r, int L, int R, int val) {
        if(!t || r<L || R<L || (seg[t].mn > val))   return limit+1;
        if(L<=l and r<=R) {
            for(int mid; l^r; ) {
                mid = (l+r)>>1;
                if(seg[t].ls and seg[seg[t].ls].mn <= val)  t = seg[t].ls, r = mid;
                else    t = seg[t].rs, l = mid+1;
            }
            return l;
        }
        int mid = (l+r)>>1;
        int res = Queryr(seg[t].ls, l, mid, L, R, val);
        return res!=limit+1 ?res :Queryr(seg[t].rs, mid+1, r, L, R, val);
    }
public:
    inline void init(int n) {
        limit = n, cnt = rt = 0;
    }
    inline void clear() {
        cnt = rt = 0;
    }
    inline void insert(int pos, int val) {
        if(!rt) newnode(rt);
        int l = 1, r = limit, t = rt;
        for(int mid; ; ) {
            seg[t].mn = min(seg[t].mn, val);
            if(l == r)  return ;
            mid = (l+r)>>1;
            if(pos <= mid) {
                if(!seg[t].ls)  newnode(seg[t].ls);
                t = seg[t].ls, r = mid;
            } else {
                if(!seg[t].rs)  newnode(seg[t].rs);
                t = seg[t].rs, l = mid+1;
            }
        }
    }
    inline int Queryl(int R, int val) {
        return Queryl(rt, 1, limit, 1, R, val);
    }
    inline int Queryr(int L, int val) {
        return Queryr(rt, 1, limit, L, limit, val);
    }
} seg;

class BinaryIndexedTree {
private:
    int tree[Maxn], limit;
    inline int lowbit(int &t) { return t&(-t); }
public:
    inline void init(int n) { limit = n; }
    inline void Add(int t, int k) {
        for(; t; t-=lowbit(t))  tree[t] += k;
    }
    inline int Ask(int t) {
        int res = 0;
        for(; t<=limit; t+=lowbit(t))   res += tree[t];
        return res;
    }
} bit;

namespace Josh_zmf {

    int N, Q, K, mcnt, bfn[Maxn], L[Maxn], R[Maxn], dep[Maxn], ans[Maxn];
    int rt, all, stk[Maxn], top, size[Maxn]; bool vis[Maxn]; queue <int> q;
    struct Que { int l, r, id; } que[Maxq];
    struct Mod { int x, y, opt; } mod[Maxn*3];

    inline void pre_bfs(int u) {
        static int num = 0; static bool bj[Maxn];
        q.push(u);
        for(; !q.empty(); ) {
            u = q.front(), q.pop();
            bj[u] = 1, bfn[u] = ++num, L[u] = 0, R[u] = N+1;
            for(int i=head[u], v; i; i=edge[i].next) {
                v = edge[i].to;
                if(bj[v])   continue;
                q.push(v);
            }
        }
        memset(bj+1, 0, N);
    }

    inline void getrt(int u, int faa) {
        static int maxx[Maxn];
        size[u] = 1, maxx[u] = 0;
        for(int i=head[u], v; i; i=edge[i].next) {
            if((v=edge[i].to)==faa || vis[v])   continue;
            getrt(v, u), size[u] += size[v];
            maxx[u] = max(maxx[u], size[v]);
        }
        maxx[u] = max(maxx[u], all - size[u]);
        if(!rt || maxx[u] < maxx[rt])   rt = u;
    }

    inline void get_bfs(int u) {
        static int bj[Maxn], tim = 0;
        q.push(u), tim++, dep[u] = 1;
        for(; !q.empty(); ) {
            u = q.front(), q.pop();
            bj[u] = tim, stk[++top] = u;
            if(dep[u] >= K+1)   continue;
            for(int i=head[u], v; i; i=edge[i].next) {
                v = edge[i].to;
                if(bj[v]==tim || vis[v])    continue;
                dep[v] = dep[u] + 1, q.push(v);
            }
        }
    }

    inline void get_dfs(int u, int faa=0) {
        stk[++top] = u, dep[u] = dep[faa] + 1;
        for(int i=head[u], v; i; i=edge[i].next) {
            v = edge[i].to;
            if(v == faa || vis[v])  continue;
            get_dfs(v, u);
        }
    }

    inline void Build(int u) {
        vis[u] = 1;
        top = 0, get_bfs(u), sort(stk+1, stk+1+top, [&](const int &a, const int &b) { return bfn[a] < bfn[b]; } ), seg.clear();
        for(int i=1, v; i<=top; i++) {
            v = stk[i];
            // printf("u:%d, v:%d, depu:%d, depv:%d\n", u, v, dep[u], dep[v]);
            if(L[v]^(v-1))  L[v] = max(L[v], seg.Queryl(v-1, K+2*dep[u]-dep[v]));
            if(R[v]^(v+1))  R[v] = min(R[v], seg.Queryr(v+1, K+2*dep[u]-dep[v]));
            // printf("L:%d, R:%d\n", L[v], R[v]);
            seg.insert(v, dep[v]);
        }
        for(int i=head[u], v; i; i=edge[i].next) {
            v = edge[i].to;
            if(vis[v])  continue;
            all = size[v], rt = 0, getrt(v, 0), Build(rt);
        }
    }

    inline int main() {
        cin>> N>> Q>> K, seg.init(N), bit.init(N+2);
        for(int u=2, v; u<=N; u++)  cin>> v, Add_edge(u, v), Add_edge(v, u);
        pre_bfs(1), all = N, rt = 0, getrt(1, 0), Build(rt);
        // for(int u=1; u<=N; u++) { L[u]++, R[u]--; }
        // for(int u=1; u<=N; u++) {
        //  printf("u:%d, bfn:%d, L:%d, R:%d\n", u, bfn[u], L[u], R[u]);
        // }
        for(int i=1; i<=Q; i++) cin>> que[i].l>> que[i].r, que[i].id = i, que[i].l++, que[i].r++;
        for(int i=1; i<=N; i++) mod[++mcnt] = {L[i]+1, i+1, 1}, mod[++mcnt] = {i+1, R[i]+1, 1}, mod[++mcnt] = {L[i]+1, R[i]+1, -1};
        sort(que+1, que+1+Q, [&](const Que &a, const Que &b) { return a.r < b.r; } );
        sort(mod+1, mod+1+mcnt, [&](const Mod &a, const Mod &b) { return a.y < b.y; } );
        for(int i=1, j=1; i<=Q; i++) {
            for(; j<=mcnt and mod[j].y<=que[i].r; j++)  bit.Add(mod[j].x, mod[j].opt);
            ans[que[i].id] = que[i].r - que[i].l + 1 - bit.Ask(que[i].l);
        }
        for(int i=1; i<=Q; i++) cout<< ans[i]<< '\n';
        return 0;
    }

}

int main() {
    Josh_zmf::main();
    return 0;
}