非常巧妙的一道题目,感谢 hzwer 学长博客的启发。

换一种角度理解树上节点的深度,一般我们将深度潜意识认为为一个数值,但是这道题目需要抽象为查询过程。具体地,对于一个节点的深度,代表着这个节点到根节点上的简单路径的节点个数。

那么题面要求一个查询 $i,z$ 的 $dep[lca]$ 可以用以下操作来统计答案:

  • 由于 $z$ 固定,我们考虑把 $z$ 作为一个查询的对象。
  • 那么对于 $i$ ,我们把从根节点到 $i$ 号节点的所有节点标记 $+1$
  • 查询 $z$ 时,只需要查询 $z$ 到根节点的标记总数即可。

对于一组 $i\in[l,r]$,也是类似以上的操作,可以考虑用树链剖分和线段树来维护。

对于这道题目,考虑差分答案,将答案差分为 $[1,r]$ 和 $[1,l-1]$ 区间的差,那么我们就不需要撤销操作了。

时间复杂度:$\mathcal O(q\log q+q\log^2 n)$

注意:笔者在代码时犯了一个错误,从 $0$ 开始标号的树链剖分的第一个 dfs,不能以默认的 $0$ 号来作为标准。

/*
 * Author: chhokmah
 * Date: 2020-08-27 21:45:39
 */
#include <bits/stdc++.h>

using namespace std;

template <typename T>
void read(T& x) {
  x = 0;
  int c = 0, f = 0;
  for (; !isdigit(c); c = getchar()) f |= c == '-';
  for (; isdigit(c); c = getchar()) x = x * 10 + (c & 15);
  x = f ? -x : x;
}

template <typename T>
void write(T x) {
  if (x < 0)
    putchar('-');
  if (x > 9)
    write(x / 10);
  putchar(x % 10 + '0');
}

const int N = 50001;
const int P = 201314;

int head[N], to[N], nxt[N];
int edgeCnt;

void addEdge(int u, int v) {
  to[++edgeCnt] = v;
  nxt[edgeCnt] = head[u];
  head[u] = edgeCnt;
}

int seg[N << 2], tag[N << 2];

void pushup(int p) {
  seg[p] = (seg[p << 1] + seg[p << 1 | 1]) % P;
}

void pushdown(int p, int l, int r) {
  if (tag[p]) {
    int mid = l + r >> 1;
    tag[p << 1] += tag[p], tag[p << 1 | 1] += tag[p];
    seg[p << 1] = (seg[p << 1] + (mid - l + 1) * tag[p]) % P;
    seg[p << 1 | 1] = (seg[p << 1 | 1] + (r - mid) * tag[p]) % P;
    tag[p] = 0;
  }
}

void update(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    seg[p] = (seg[p] + r - l + 1) % P;
    tag[p]++;
    return;
  }
  pushdown(p, l, r);
  int mid = l + r >> 1;
  if (ql <= mid)
    update(p << 1, l, mid, ql, qr);
  if (qr > mid)
    update(p << 1 | 1, mid + 1, r, ql, qr);
  pushup(p);
}

int ask(int p, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr)
    return seg[p];
  pushdown(p, l, r);
  int mid = l + r >> 1, res = 0;
  if (ql <= mid)
    res += ask(p << 1, l, mid, ql, qr);
  if (qr > mid)
    res += ask(p << 1 | 1, mid + 1, r, ql, qr);
  return res % P;
}

int n, q;
int sz[N], fa[N], hvy[N], top[N], tin[N], tout[N], dep[N];
int dfc;

void dfs(int u, int Fa) {
  fa[u] = Fa;
  sz[u] = 1;
  hvy[u] = -1;
  dep[u] = dep[Fa] + 1;
  for (int e = head[u]; e; e = nxt[e]) {
    int v = to[e];
    dfs(v, u);
    sz[u] += sz[v];
    if (hvy[u] == -1 || sz[v] > sz[hvy[u]])
      hvy[u] = v;
  }
}

void Dfs(int u, int Top) {
  tin[u] = dfc++;
  top[u] = Top;
  if (hvy[u] != -1)
    Dfs(hvy[u], Top);
  for (int e = head[u]; e; e = nxt[e]) {
    int v = to[e];
    if (v != hvy[u])
      Dfs(v, v);
  }
  tout[u] = dfc;
}

void add(int x) {
  while (x != -1) {
    update(1, 0, n - 1, tin[top[x]], tin[x]);
    x = fa[top[x]];
  }
}

int query(int x) {
  int res = 0;
  while (x != -1) {
    res = (res + ask(1, 0, n - 1, tin[top[x]], tin[x])) % P;
    x = fa[top[x]];
  }
  return res;
}

struct Query {
  int id, x, z, type;

  bool operator<(const Query& rhs) const {
    return x < rhs.x;
  }
} qry[N << 1];

int qcnt;
int ans[N];

int main() {
  read(n), read(q);
  for (int i = 1, u; i < n; i++) {
    read(u);
    addEdge(u, i);
  }
  dfs(0, -1);
  Dfs(0, 0);
  for (int i = 0, l, r, z; i < q; i++) {
    read(l), read(r), read(z);
    qry[qcnt++] = (Query){i, l - 1, z, -1};
    qry[qcnt++] = (Query){i, r, z, 1};
  }
  sort(qry, qry + qcnt);
  int p = 0;
  for (int i = 0; i < n; i++) {
    add(i);
    while (p < qcnt && qry[p].x == -1)
      p++;
    while (p < qcnt && qry[p].x <= i) {
      ans[qry[p].id] += qry[p].type * query(qry[p].z);
      if (ans[qry[p].id] < 0)
        ans[qry[p].id] += P;
      p++;
    }
    if (p == qcnt)
      break;
  }
  for (int i = 0; i < q; i++)
    write(ans[i] % P), puts("");
  return 0;
}
最后修改:2020 年 08 月 28 日 12 : 03 AM
如果觉得我的文章对你有用,请随意赞赏