线段树合并 & 分裂（二）

ShiRoZeTsu · 2023-10-11 22:52:41 · 个人记录

有了第一篇，所以就要有第二篇啦

以下是习题：

• P3899 [湖南集训] 更为厉害
• CF1009F Dominant Indices
• CF570D Tree Requests
• CF246E Blood Cousins Return

P3899 [湖南集训] 更为厉害

简要题意：给定一棵有根树，每次给定一组 a, k，求有多少个二元组 (b, c) 满足：

解法

由于 k 会发生变化，所以先预处理再回答询问的思路肯定行不通，因为至少要 \mathcal{O}(n^2)。

考虑把 a 固定，不难发现 b 要么是 a 的祖先，要么是 a 的后代。可以分情况讨论一下：

• 如果 b 是 a 的祖先，那么 a 的子树上所有点（不包括 a 自己）都可以是 c，此时合法的 c 共有 (sze_a - 1) 个；

• 如果 b 是 a 的后代，那么 b 的子树上所有点（不包括 b 自己）都可以是 c，此时合法的 c 共有 (sze_b - 1) 个。

然后我们就可以统计答案：

• 对于第一种情况，不妨设 a 的深度为 dep_a（根节点深度为 1），那么 a 的上方，合法的 b 的数量共有 \min(dep_a - 1, k) 个。那么这样的 (b, c) 共有 \min(dep_a - 1, k) \times (sze_a - 1) 个。

• 对于第二种情况，不妨设 a 的深度为 dep_a（根节点深度为 1），那么 a 的下方，合法的 b 的深度一定在 dep_a + 1 至 dep_a + k 之间，因此这样的 (b, c) 共有 \sum_{dep_a + 1 \leq dep_b \leq dep_a + k} (sze_b - 1) 个。

所以总的答案为：

前面那个东西可以直接算，主要瓶颈在后半部分。

实际上后半部分可以看成一个区间求和，那么自然可以用线段树去维护。

然后在 dfs 的时候合并上来，并把当前点 u 的贡献加进去，也就是在 dep_u 的位置单点加 sze_u - 1。

代码很好写。

CODE：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;

const int maxn = 3e5 + 5;

int n, q;
int dep[maxn], sze[maxn], root[maxn];
ll ans[maxn];

struct edge {
    int to, nxt;
} e[maxn<<1];

int tot = 1, head[maxn];
void addedge(int u, int v) {
    e[++tot].to = v;
    e[tot].nxt = head[u];
    head[u] = tot;
}

struct node {
    int k, id;
};
vector<node> ask[maxn];

#define mid ((l + r) >> 1)

int cnt, top;
int stk[maxn<<5];
int ls[maxn<<2], rs[maxn<<2];
ll sum[maxn<<2];

int newnode() {
    if(top) {
        int x = stk[top];
        top--;
        return x;
    }
    else return ++cnt;
}

void del(int o) {
    ls[o] = rs[o] = sum[o] = 0;
    stk[++top] = o;
}

void merge(int& o, int p, int l, int r) {
    if(!o || !p) { o += p; return; }
    if(l == r) { sum[o] += sum[p]; del(p); return; }
    merge(ls[o], ls[p], l, mid);
    merge(rs[o], rs[p], mid+1, r);
    sum[o] = sum[ls[o]] + sum[rs[o]];
    del(p);
}

void modify(int& o, int l, int r, int pos, ll val) {
    if(!o) o = newnode();
    if(l == r) { sum[o] += val; return; }
    if(pos <= mid) modify(ls[o], l, mid, pos, val);
    else modify(rs[o], mid+1, r, pos, val);
    sum[o] = sum[ls[o]] + sum[rs[o]];
}

ll query(int& o, int l, int r, int ql, int qr) {
    if(ql <= l && r <= qr) return sum[o];
    ll res = 0;
    if(ql <= mid) res += query(ls[o], l, mid, ql, qr);
    if(mid < qr) res += query(rs[o], mid+1, r, ql, qr);
    return res;
}

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    sze[u] = 1;
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u);
        sze[u] += sze[v];
        merge(root[u], root[v], 1, n);
    }
    modify(root[u], 1, n, dep[u], sze[u]-1);
    for(int i = 0; i < ask[u].size(); i++) {
        int k = ask[u][i].k, id = ask[u][i].id;
        ans[id] = 1ll * min(dep[u]-1, k) * (sze[u] - 1);
        ans[id] += query(root[u], 1, n, dep[u]+1, min(dep[u]+k, n));
    }
}

int main() {
    scanf("%d %d", &n, &q);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addedge(u, v); addedge(v, u);
    }
    for(int i = 1; i <= q; i++) {
        int p, k;
        scanf("%d %d", &p, &k);
        ask[p].push_back((node){k, i});
    }
    dfs(1, 0);

    for(int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return 0;
}

CF1009F Dominant Indices

简要题意：给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u 子树中到 u 距离为 x 的节点数。 对于每个点，求一个最小的 k，使得 d(u,k) 最大。

解法

这道题相对于上一道题来说难度小了不少，还是很板子的。

具体做法就是，用线段树维护子树中，每种深度的点的出现次数，以及出现次数最多的最小深度。

然后 dfs，合并线段树之后用查询的答案减去当前点的深度即可。

不过这道题有一个小亮点：1 \leq n \leq 10^6。

在第一次写完提交之后，我在 #131 RE 了好几次，最后发现空间开小了，但是实际上我已经全部开到了 maxn \times 2^5 空间理应来说已经很大了。

哪里出问题了呢？

我仔细地检查了我的代码，发现了这样一个细节：

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
//* build(root[u], 1, n, dep[u]);
    for(int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if(v == fa) continue;
        dfs(v, u);
        merge(root[u], root[v], 1, n);
    }
    ans[u] = mn[root[u]] - dep[u];
}

注意打 * 的那一行，每次调用 build 函数都会新建一棵线段树。由于只有一个点，所以会占用 \log n 的空间。

然后我们考虑，当树退化成一条链的时候，会发生什么。