Educational Codeforces Round 138

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
F(Fenwick,树)

https://codeforces.com/contest/1749

F. Distance to the Path

给一定n点树, 初始每个点的值为0

m 个询问, 两种操作

  1. 输出点v的值
  2. 对所有到路径u..v 距离小于d的点 +k

范围

n 2e5

m 2e5

d [0,20]

k [1,1000]

4s

512mb

我的思路

如果 d = 0, 就是每次对路径上的点 增加k

似乎可以树上差分+lca维护?

但实际上 中间穿插着求一个点的值, 这样每次求值还是 O(dep[u]), 并不可行

怎么有点 树链剖分的味道?

树链剖分+线段树维护每个链???

那么 d != 0 ??

似乎会变成菊花状

题解

先随便选根, 那么对v距离 <= d 的 , 就是 v的子树距离恰好=d的点 +k, 比如d=0 就是v自身, d=1就是v的所有儿子(不处理它自身

// 这样父向的似乎还有点问题?

令 p[v] = v的父节点, p^2[v] = p[p[v]], p^n[v]=p[p^n-1[v]], p^0[v]=v

然后 只需要在 v 上+k, 这样查询u的时候 ans[p^d[u]] ???

然后d很小, 所以 for i=0..d: ans+=ans_i[p^i[u]]

转化题目中的 到 u…v 距离小于等于d的点 +k

l = lca(u,v)

分别考虑[v..l) 和 [u..l)

v子树中距离d的需要+k

p[v] 子树中距离d的需要+k,注意到这里会覆盖到v子树中距离d-1的点!

p^2[v] 子树中距离d的需要+k,注意到这里会覆盖到v子树中距离d-2的点 和 p[v]子树中距离d-1的点!!

这样处理完以后, 还剩一些

  • l 子树 中距离 d, d-1,…,0 的点, 这里会覆盖掉 [v..l) 中那些深度浅距离短的点
  • p[l] 子树 中距离 d-1,…,0 的点, 这里有问题, 这里会和 l 子树中距离d-2的点有重复, 下面同样有重复的问题在
  • p^2[l] 子树 中距离 d-2,…,0 的点
  • p^d[l] 子树 中距离 0 的点

要去掉重复

  • l 子树中距离 d, d-1的点
  • p[l] 中距离 d-1, d-2 的点
  • p^i[l] 中距离 d-i, d-i-1 的点

这部分最多2d个操作

综上, 需要,

  1. 路径上的距离d标识的加k val[u..v][d]+=k
  2. 某一个点 的某个d + k
  3. 询问v上的值

fenwick + (tin,tout)

如果一个点 x 在 [u…l ) 上, l是u的祖先

那么按照展开 tin[l]...tin[x]...tin[u]...tout[u]...tout[x]...tout[l]

也就是tin[x]..tout[x]包含了u 而没有包含l, 如果不在这个链上, 那么要么同时包含 tin[l],tin[u] 比如是l的祖先, 要么同时不包含(是l的子树中,但不在链上u兄弟(tin[u]..tout[u] 外)关系或子关系(tin[u]..tout[u] 内))

所以可以tin[u]+=k, tin[v]-=k, 就完成了链的处理, 这样查询 只需要tin[x]...tout[x]

然后这里 还在 选的点向上构建了长度d 的点 用来减少if判断, 并作为新的root

代码

https://codeforces.com/contest/1749/submission/188816870

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

int read(){int r;scanf("%d",&r);return r;}

const int LOG = 18;
const int D = 21;
const int N = 200000+D;

int n;
vector<int> g[N+10];

int p[LOG][N+10]; // p[pwr][u];
int tin[N+10], tout[N+10];

void build(int v, int f,int &T) {
  tin[v] = T++;
  p[0][v] = f;
  rep(pw, 1, LOG) p[pw][v] = p[pw-1][p[pw-1][v]]; // 倍增
  for (int u: g[v]) if(u!=f) build(u, v, T);
  tout[v] = T; // [tin[v] ...... tout[v]] 都是v的子树
}

bool inside(int l, int v) { return tin[l] <= tin[v] && tout[v] <= tout[l]; }

int lca(int u, int v) {
  if (inside(u, v)) return u;
  if (inside(v, u)) return v;
  per(pw,0,LOG) if (!inside(p[pw][u], v)) u = p[pw][u];
  return p[0][u];
}

struct Fenwick {
  int n;
  vector<int> F;
  void init(int nn) { // 0-index support
    n = nn;
    F.assign(n, 0);
  }

  void add(int pos, int val) {
    for (; pos < n; pos |= pos + 1) F[pos] += val;
  }
  int sum(int pos) {
    int ans = 0;
    for (; pos >= 0; pos = (pos & (pos + 1)) - 1) ans += F[pos];
    return ans;
  }
  int getSum(int l, int r) { return sum(r-1) - sum(l-1); }
};

struct DS {
  Fenwick f;
  void init(int n) { f.init(n); }
  // x in path [v...l)
  //    tin[l]..tin[x]..tin[u]..tout[u]..tout[x]..tout[l]
  // x not in path [v...l)
  //    tin[x]..tin[l]..tin[u]..tout[u]..tout[l]..tout[x]
  //    tin[l]..tin[u]..tin[x]..tout[x]..tout[u]..tout[l]
  //    tin[l]..tin[x]..tout[x]..tin[u]..tout[u]..tout[l]
  //    tin[l]..tin[u]..tout[u]..tin[x]..tout[x]..tout[l]
  void addPath(int v, int l, int k) {
    f.add(tin[v], +k);
    f.add(tin[l], -k);
  }
  int getVertex(int v) { return f.getSum(tin[v], tout[v]); }
};

DS t[D]; // t[distance] => fenwick

int main() {
  n=read();
  rep(i,0,n-1) {
    int u=read()-1;
    int v=read()-1;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  // n+d-1 -> ... -> n+2->n+1->n->n-1, 从n-1 向上构建 d个点, 减少if判断, 统一同样操作
  rep(i,0,D) g[n+i].push_back(n+i-1);
  int root=n+D-1; // 新建的点

  int T=0;
  build(root, root, T);
  rep(i, 0, D) t[i].init(root + 1);

  int m=read();
  while(m--){
    int op=read();
    if (op == 1) {
      int v=read()-1;
      int ans = 0;
      rep(i,0,D){
        ans += t[i].getVertex(v);
        v = p[0][v];
      }
      printf("%d\n",ans);
    } else { // op == 2;
      int u=read()-1;
      int v=read()-1;
      int k=read();
      int d=read();
      int l = lca(u, v);

      if (u != l) t[d].addPath(u, l, k);
      if (v != l) t[d].addPath(v, l, k);

      rep(i,0,d+1){ // l 向上
        t[d-i].addPath(l,p[0][l],k);
        if (d-i-1 >= 0) t[d-i-1].addPath(l,p[0][l],k);
        l=p[0][l];
      }
    }
  }
  return 0;
}

总结

F

这个 <= d 反过去 变成 每个具体的 =d 的变形就很可以

然后 重复统计的问题其实不要怕, 仔细一想其实还是很显然的, 就可以拆分了

最后就是 树通过遍历化成数组 的区间操作了, 这就是树化数组 和 链的 批量加法, 和点查询问题了

参考

官方