现在才做这题TAT

如果询问的是一个子集和\(z\)的所有LCA的深度的和，那可以把子集里每一个元素到根的路径全部加1，然后根到\(z\)的路径上的和就是答案。

如果是区间的话，每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间，然后离线，给询问排个序然后就好做了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
using ll = long long;
const ll ha = 201314LL;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
  G[u].push_back(v);
  G[v].push_back(u);
}

const int maxno = maxn << 2;
ll sumv[maxno], addv[maxno];
void maintain(int o) {
  sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;
}
void paint(int o, int L, int R, ll v) {
  v %= ha;
  addv[o] += v; addv[o] %= ha;
  sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;
}
void pushdown(int o, int L, int R) {
  if(addv[o] != 0LL) {
    ll v = addv[o]; addv[o] = 0;
    int M = (L + R) / 2;
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, L, M, v); paint(rc, M + 1, R, v);
  }
}
int ql, qr; ll v;
void modify(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    paint(o, L, R, v);
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    if(ql <= M) modify(o << 1, L, M);
    if(qr > M) modify(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
ll query(int o, int L, int R) {
  if(ql <= L && R <= qr) {
    return sumv[o];
  } else {
    pushdown(o, L, R);
    int M = (L + R) / 2;
    ll ans = 0;
    if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha;
    if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha;
    return ans;
  }
}

int siz[maxn], fa[maxn], dep[maxn], hson[maxn];
void dfs_1(int x, int f = 0, int depth = 0) {
  fa[x] = f; dep[x] = depth; siz[x] = 1;
  int maxs = 0;
  for(auto v : G[x]) {
    if(v != f) {
      dfs_1(v, x, depth + 1);
      siz[x] += siz[v];
      if(siz[v] > maxs) {
        maxs = siz[v]; hson[x] = v;
      }
    }
  }
}
int top[maxn], tid[maxn], dfn[maxn];
void dfs_2(int x, int a) {
  static int cnt = 0; cnt ++;
  top[x] = a; tid[cnt] = x; dfn[x] = cnt;
  if(hson[x]) {
    dfs_2(hson[x], a);
  } else {
    return;
  }
  for(auto v : G[x]) {
    if(v != fa[x] && v != hson[x]) {
      dfs_2(v, v);
    }
  }
}

int n;
void update(int x, int y, const ll &delta) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y]; v = delta;
    modify(1, 1, n); return;
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x]; v = delta;
  modify(1, 1, n);
  update(fa[top[x]], y, delta);
}
ll query(int x, int y) {
  if(top[x] == top[y]) {
    if(dfn[x] > dfn[y]) std::swap(x, y);
    ql = dfn[x], qr = dfn[y];
    return query(1, 1, n);
  }
  if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
  ql = dfn[top[x]], qr = dfn[x];
  ll ret = query(1, 1, n);
  return (ret + query(fa[top[x]], y)) % ha;
}

struct Q {
  int l, z;
  int id; ll p;
  bool operator <(const Q &res) const {
    if(l == res.l) {
      return id < res.id;
    } else {
      return l < res.l;
    }
  }
};
Q que[maxn << 1];
ll ans[maxn];

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 2; i <= n; i ++) {
    int f; scanf("%d", &f); f ++;
    add_edge(f, i);
  }
  dfs_1(1); dfs_2(1, 1);
  for(int i = 1; i <= q; i ++) {
    int l, r, z; scanf("%d%d%d", &l, &r, &z);
    l ++; r ++; z ++;
    Q &L = que[i * 2 - 1]; Q &R = que[i * 2];
    L.id = R.id = i; L.p = -1; R.p = 1;
    L.z = R.z = z; L.l = l - 1; R.l = r;
  }
  std::sort(que + 1, que + 1 + 2 * q);
  int p = 0;
  for(int i = 1; i <= 2 * q; i ++) {
    const Q &t = que[i];
    while(p < t.l) {
      p ++; update(1, p, 1);
    }
    ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha;
  }
  for(int i = 1; i <= q; i ++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

• 相关文章
• 全局相关文章