CodeChef好（du）题（liu）选做

发表于 | 分类于

近期看了一些先辈的文章……柑橘要刷一些CC力，，，

怕不是有一半题都是毒瘤数据结构？

QTREE6 Query on a tree VI

Description

有一棵\(n\)个点的有颜色的树，初始时每一个点都是白色。要求你支持以下两种操作（共\(m\)次）：

  • 0 u：查询\(u\)所在的连通块有几个点。这里的话一条边当且仅当两边颜色一样才会生效。
  • 1 u：翻转\(u\)的颜色。

\(1\leq n, m\leq 10^5\)。

Solution

记得大约一年前多听过一个挺毒瘤的树剖做法……然而柑橘还事动态树简单哎。

把每个点拆成白点和黑点，每个点如果是白色的那么他的白点向父亲连边，反之亦然，并且两者只能择其一。可以发现如果一个点所在的森林的根是同色的话那么就取根的子树大小就行了，其他情况特判一下取下面一个点。

然后还剩下一个问题就是在动态树上维护子树大小……这个的当然可以直接ETT，不过我从来没写过LCT维护子树信息所以就用了LCT。LCT维护子树信息倒也简单，就在每个Splay结点上额外开个域维护它的虚儿子信息就行了，access和link-cut的时候再修改一下这个信息，然后就做完了……

Code

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
struct Node {
  Node *fa, *ch[2];
  int vs, s;
  
  int d() {
    return (this == fa -> ch[1]);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c; c -> fa = this;
  }
  void maintain() {
    s = ch[0] -> s + ch[1] -> s + vs;
  }
};
const int maxn = 100005;
Node pool[maxn << 1];
Node *nil, *cur;
void init_pool() {
  nil = cur = pool;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  nil -> vs = nil -> s = 0;
}
Node *T(int x, int col) {
  return pool + (2 * x - col);
}
int id(Node *x) {
  return (x - pool + 1) / 2;
}
void refresh(Node *x) {
  x -> vs = x -> s = 1;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  int d = x -> d(); Node *y = x -> fa;
  y -> sc(x -> ch[d ^ 1], d); y -> maintain();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  x -> sc(y, d ^ 1); x -> maintain();
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
  x -> maintain();
}
Node *access(Node *x) {
  Node *v = x, *y = nil;
  while(x != nil) {
    splay(x);
    x -> vs -= y -> s - x -> ch[1] -> s;
    x -> sc(y, 1); x -> maintain();
    y = x; x = x -> fa;
  }
  splay(v);
  return v;
}
void link(Node *fa, Node *x) {
  access(fa); access(x);
  x -> fa = fa; fa -> vs += x -> s;
  fa -> maintain();
}
void cut(Node *x) {
  access(x);
  x -> ch[0] -> fa = nil;
  x -> ch[0] = nil;
  x -> maintain();
}
Node *get_root(Node *x) {
  access(x);
  Node *ret = x;
  while(ret -> ch[0] != nil) ret = ret -> ch[0];
  splay(ret);
  return ret;
}

std::vector<int> G[maxn];
int fa[maxn];
void dfs(int x, int a = -1) {
  fa[x] = a;
  for(auto v : G[x]) {
    if(v != a) {
      dfs(v, x);
      link(T(x, 0), T(v, 0));
    }
  }
}

bool col[maxn];
void toogle(int x) {
  col[x] = !col[x];
  if(x == 1) return;
  int d = !col[x];
  cut(T(x, d)); link(T(fa[x], 1 ^ d), T(x, 1 ^ d));
}
int query(int x) {
  int d = col[x];
  Node *rt = get_root(T(x, d));
  int ans = rt -> s;
  if(col[id(rt)] != d) {
    access(rt);
    splay(T(x, d));
    ans = T(x, d) -> s;
  }
  return ans;
}
int main() {
  int n; scanf("%d", &n);
  for(int i = 1; i <= n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  init_pool();
  for(int i = 1; i <= n; i ++) {
    refresh(T(i, 0)); refresh(T(i, 1));
  }
  dfs(1);
  int m; scanf("%d", &m);
  while(m --) {
    int op, u; scanf("%d%d", &op, &u);
    if(op == 0) {
      printf("%d\n", query(u));
    } else {
      toogle(u);
    }
  }
  return 0;
}

FNCS Chef and Churu

Description

你有一个长度为\(n\)的数字序列\(A\)，以及一个长度为\(n\)的函数序列\(F\)（\(F_i\)定义为\(\sum_{k = L_i}^{R_i} A_k\)）。要求你支持以下两种操作：

  • 1 x y：将\(A_i\)变成\(y\)。
  • 2 l r：求\(\sum_{i = l}^r F_i\)。

\(1\leq n\leq 10^5, 1\leq A_i, y\leq 10^9\)。

Solution

很显然常规数据结构无能为力……那就毒瘤分块吧！其实这是我做的第一道不水的分块题……

我们考虑对序列\(F\)分块。这样的话查询倒还好说，整块的话直接加，散块的话暴力扫一下用树状数组求和。那修改咋整？

修改对散块的影响不需要考虑，只需要考虑对整块的影响。我们可以扫每一个块，然后考虑修改对答案的影响。假设这个修改使得\(A_i\)变大了\(d\)，那么对于一个块\(k\)其答案就会变大\(\mathrm{cnt}_{k, i}d\)，其中\(\mathrm{cnt}_{k, i}\)表示块\(k\)中有多少个函数包含了位置\(i\)，这个可以在预处理时很容易的用差分搞出来。

还有一点就是你用long long会溢出……要开unsigned long long。

Code

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
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
const int maxn = 100005;
typedef unsigned long long ll;
inline int lowbit(int x) {
  return x & (-x);
}
int A[maxn]; ll C[maxn]; int n;
void add(int p, int v) {
  A[p] += v;
  while(p <= n) {
    C[p] += v;
    p += lowbit(p);
  }
}
ll sum(int p) {
  ll ans = 0;
  while(p > 0) {
    ans += C[p];
    p -= lowbit(p);
  }
  return ans;
}
ll qs(int l, int r) {
  return sum(r) - sum(l - 1);
}

const int max_num = 317;
int cnt[max_num][maxn]; ll S[max_num];
int seg[maxn][2];
int blk_siz, blk_num;
void process() {
  blk_siz = floor(sqrt((double)n));
  blk_num = ceil((double)n / (double)blk_siz);
  for(int i = 0; i < blk_num; i ++) {
    for(int j = i * blk_siz; j < std::min(n, (i + 1) * blk_siz); j ++) {
      int l = seg[j][0], r = seg[j][1];
      S[i] += qs(l, r);
      cnt[i][l] ++; cnt[i][r + 1] --;
    }
    for(int j = 1; j <= n; j ++) cnt[i][j] += cnt[i][j - 1];
  }
}
void update(int p, int v) {
  add(p, v);
  for(int i = 0; i < blk_num; i ++) {
    S[i] += (long long)cnt[i][p] * (long long)v;
  }
}
ll query(int l, int r) {
  int lb = l / blk_siz, rb = r / blk_siz;
  if(lb == rb) {
    ll ans = 0;
    for(int i = l; i <= r; i ++) {
      ans += qs(seg[i][0], seg[i][1]);
    }
    return ans;
  } else {
    ll ans = 0;
    for(int i = l; i < std::min(n, (lb + 1) * blk_siz); i ++) {
      ans += qs(seg[i][0], seg[i][1]);
    }
    for(int i = rb * blk_siz; i <= r; i ++) {
      ans += qs(seg[i][0], seg[i][1]);
    }
    for(int i = lb + 1; i < rb; i ++) {
      ans += S[i];
    }
    return ans;
  }
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int x; scanf("%d", &x);
    add(i, x);
  }
  for(int i = 0; i < n; i ++) {
    scanf("%d%d", &seg[i][0], &seg[i][1]);
  }
  process();
  int Q; scanf("%d", &Q);
  while(Q --) {
    int op, a, b; scanf("%d%d%d", &op, &a, &b);
    if(op == 1) {
      update(a, b - A[a]);
    } else {
      printf("%llu\n", query(a - 1, b - 1));
    }
  }
  return 0;
}

MONOPOLY Gangsters of Treeland

Description

有一棵\(n\)个点的点有颜色的树，以\(0\)为根，初始时任意两点颜色不同。一条边在两边颜色不一样时边权为1，其他情况下为0。

现在要求你支持两种操作：

  • O u：搞出来一种全新的颜色，然后把\(u\)到根上所有点都染上该颜色。
  • q u：求\(u\)所在子树所有点到根路径长度的平均值。

Solution

感觉像是某些套路的万恶之源？

我们把两边颜色不一样的边看成虚边，其他看成实边，那么到根路径长度就是到根路径虚边数量。初始时整个树全是虚边。

然后我们发现第一种操作其实和access一模一样……所以用线段树+DFS序维护子树权值，access的时候改一下，然后没了……

Code

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 100005;
using ll = long long;
using R = double;
std::vector<int> G[maxn];
void init_graph() {
  for(int i = 0; i < maxn; i ++) G[i].clear();
}
void add_edge(int u, int v) {
  G[u].push_back(v);
}
void ins_edge(int u, int v) {
  add_edge(u, v); add_edge(v, u);
}

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

int dfn[maxn], siz[maxn];
struct Node {
  Node *fa, *ch[2];
  int id, l;
  int d() {
    return (this == fa -> ch[1]);
  }
  void sc(Node *c, int dir) {
    ch[dir] = c; c -> fa = this;
  }
  void maintain() {
    if(ch[0] -> id) {
      l = ch[0] -> l;
    } else {
      l = id;
    }
  }
};
Node pool[maxn]; Node *nil;
void init_pool() {
  nil = pool;
  nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  nil -> id = nil -> l = 0;
}
#define T(x) (pool + (x))
void refresh(Node *x, int id = 0) {
  x -> id = x -> l = id;
  x -> fa = x -> ch[0] = x -> ch[1] = nil;
}

bool is_root(Node *x) {
  return (x -> fa == nil || (x -> fa -> ch[0] != x && x -> fa -> ch[1] != x));
}
void zig(Node *x) {
  int d = x -> d(); Node *y = x -> fa;
  y -> sc(x -> ch[d ^ 1], d); y -> maintain();
  if(is_root(y)) {
    x -> fa = y -> fa;
  } else {
    y -> fa -> sc(x, y -> d());
  }
  x -> sc(y, 1 ^ d); x -> maintain();
}
void splay(Node *x) {
  while(!is_root(x)) {
    Node *y = x -> fa;
    if(!is_root(y)) {
      if((x -> d()) ^ (y -> d())) {
        zig(x);
      } else {
        zig(y);
      }
    }
    zig(x);
  }
}

int n;
void add_tree(int x, ll v) {
  if(x == 0) return;
  int l = dfn[x], r = dfn[x] + siz[x] - 1;
  update(1, 1, n, l, r, v);
}
Node *get_root(Node *x) {
  while(x -> ch[0] != nil) {
    x = x -> ch[0];
  }
  splay(x);
  return x;
}
Node *access(Node *x) {
  Node *v = x, *y = nil;
  while(x != nil) {
    splay(x);
    add_tree(x -> ch[1] -> l, 1);
    add_tree(y -> l, -1);
    x -> sc(y, 1);
    y = x; x = x -> fa;
  }
  splay(v);
  return v;
}
R query(int x) {
  int l = dfn[x], r = dfn[x] + siz[x] - 1;
  return (R)query(1, 1, n, l, r) / (R(siz[x]));
}

int cnt;
void dfs(int x, int fa = -1) {
  dfn[x] = ++ cnt; siz[x] = 1;
  refresh(T(x), x);
  for(int v : G[x]) {
    if(v != fa) {
      dfs(v, x);
      siz[x] += siz[v];
      T(v) -> fa = T(x);
      add_tree(v, 1);
    }
  }
}

int main() {
  init_pool();
  int T; scanf("%d", &T);
  while(T --) {
    init_graph();
    scanf("%d", &n); ref_tree(1, 1, n);
    for(int i = 1; i <= n - 1; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      u ++; v ++;
      ins_edge(u, v);
    }
    cnt = 0; dfs(1);
    int Q; scanf("%d", &Q);
    while(Q --) {
      char op[5]; int u; scanf("%s%d", op, &u);
      u ++;
      if(op[0] == 'O') {
        access(T(u));
      } else {
        printf("%.10lf\n", query(u));
        fflush(stdout);
      }
    }
  }
  return 0;
}