QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#662374#7626. Quake and Rebuildnhuang685RE 458ms4672kbC++234.6kb2024-10-20 23:29:002024-10-20 23:29:00

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-10-20 23:29:00]
  • 评测
  • 测评结果:RE
  • 用时:458ms
  • 内存:4672kb
  • [2024-10-20 23:29:00]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-10-19 17:11:02
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

constexpr int BL = 450;

int start(int val) { return val / BL * BL; }
int end(int val) { return (val / BL + 1) * BL - 1; }

struct Arr {
  std::vector<int> arr, la;
  Arr() = default;
  explicit Arr(int n) : arr(n), la(n / BL) {}
  void add(int i, int v) { arr[i] += v; }
  void set(int i, int v) { arr[i] = v - la[i / BL]; }
  void add_i(int i, int v) { la[i] += v; }
  int get(int i) const { return std::max(0, arr[i] + la[i / BL]); }
  int operator[](int i) const { return get(i); }
};
struct RBArr {
  std::vector<int> arr, la;
  RBArr() = default;
  explicit RBArr(int n) : arr(n) {}
  void add(int i, int v) {
    if (arr[i] == 0) {
      la.push_back(i);
    }
    arr[i] += v;
  }
  void set(int i, int v) {
    if (arr[i] == 0) {
      la.push_back(i);
    }
    arr[i] = v;
  }
  const int& operator[](int i) const { return arr[i]; }
  void reset() {
    for (int i : la) {
      arr[i] = 0;
    }
    la.clear();
  }
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int nn, m;
  std::cin >> nn >> m;
  int n = (nn + BL - 1) / BL * BL;
  Arr fa(n), nxt(n);
  for (int i = 1; i < nn; ++i) {
    int v;
    std::cin >> v;
    --v;
    fa.set(i, v);
  }
  std::vector<int> cnt(n);
  auto recomp = [&](int ind) {
    for (int i = BL * ind; i < BL * (ind + 1); ++i) {
      if (fa[i] < BL * ind) {
        nxt.set(i, fa[i]);
        cnt[i] = 1;
      } else {
        nxt.set(i, nxt[fa[i]]);
        cnt[i] = cnt[fa[i]] + 1;
      }
    }
    cnt[BL * ind] = 1;
  };
  for (int i = 1; i < n / BL; ++i) {
    recomp(i);
  }

  auto sub = [&](int l, int r, int d) {
    if (l / BL == r / BL) {
      for (int i = l; i <= r; ++i) {
        fa.add(i, -d);
      }
      recomp(l / BL);
      return;
    }
    for (int i = l; i <= end(l); ++i) {
      fa.add(i, -d);
    }
    recomp(l / BL);
    for (int i = end(l) + 1; i < start(r); i += BL) {
      bool re = fa.la[i / BL] > -BL;
      fa.add_i(i / BL, -d);
      if (re) {
        recomp(i / BL);
      } else {
        nxt.add_i(i / BL, -d);
      }
    }
    for (int i = start(r); i <= r; ++i) {
      fa.add(i, -d);
    }
    recomp(r / BL);
  };
  auto lca = [&](int a, int b) {
    while (nxt[a] != nxt[b]) {
      if (a < b) {
        std::swap(a, b);
      }
      a = nxt[a];
    }
    if (a / BL != b / BL) {
      return nxt[a];
    }
    while (a != b) {
      if (a < b) {
        std::swap(a, b);
      }
      a = fa[a];
    }
    return a;
  };
  RBArr freq(n);
  auto query = [&](const std::vector<int>& b) -> int {
    int l = b[0];
    for (int i = 1; i < std::ssize(b); ++i) {
      l = lca(l, b[i]);
    }
    std::vector<std::vector<int>> gr(n / BL);
    for (int i : b) {
      gr[i / BL].push_back(i);
    }
    int ans = 0;
    for (int i = n / BL - 1; i >= 0 && l <= (i + 1) * BL - 1; --i) {
      if (gr[i].empty()) {
        continue;
      }
      freq.reset();
      std::vector<int> ele;
      for (int j : gr[i]) {
        freq.add(j, 1);
        if (freq[j] == 1) {
          ele.push_back(j);
        }
      }

      freq.reset();
      bool two = false;
      for (int j : ele) {
        freq.add(nxt[j], 1);
        if (freq[nxt[j]] >= 2) {
          two = true;
        }
      }
      if (!two && l < i * BL) {
        for (int j : ele) {
          gr[nxt[j] / BL].push_back(nxt[j]);
          ans += cnt[j];
        }
        continue;
      }
      freq.reset();
      for (int j : ele) {
        freq.add(j, 1);
      }
      for (int j = (i + 1) * BL - 1; j >= std::max(l, i * BL); --j) {
        if (freq[j] == 0) {
          continue;
        }
        ++ans;
        if (fa[j] >= i * BL) {
          freq.add(fa[j], 1);
        } else {
          gr[fa[j] / BL].push_back(fa[j]);
        }
      }
    }
    return ans;
  };

  while ((m--) != 0) {
    int op;
    std::cin >> op;
    if (op == 1) {
      int l, r, d;
      std::cin >> l >> r >> d;
      --l;
      --r;
      sub(l, r, d);
    } else {
      int k;
      std::cin >> k;
      std::vector<int> b(k);
      for (int& i : b) {
        std::cin >> i;
        --i;
      }
      std::cout << query(b) << '\n';
    }
  }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

4 5
1 2 2
2 2 1 4
1 2 3 1
2 3 2 3 4
1 4 4 1
2 2 3 4

output:

3
4
3

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 412ms
memory: 3696kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: 0
Accepted
time: 363ms
memory: 3892kb

input:

6173 198631
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 ...

output:

2819
1049
1155
831
722
5962
123
624
554
601
241
597
81
29
34
390
350
443
385
6038
6083
258
5
315
27
281
6029
300
6136
322
227
46
271
263
26
268
257
6101
5816
255
258
156
243
270
186
6099
16
13
5435
163
7
35
219
182
214
10
24
23
194
178
188
183
200
167
158
197
24
189
131
35
167
24
189
15
183
176
6050...

result:

ok 30261 lines

Test #5:

score: 0
Accepted
time: 372ms
memory: 4036kb

input:

9724 198809
1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...

output:

24
25
31
31
27
25
29
23
23
21
26
23
21
24
23
23
26
26
21
24
27
23
23
23
20
19
20
18
28
25
26
21
19
21
21
26
20
23
17
20
18
21
22
22
18
21
25
18
17
18
24
18
16
18
19
24
20
18
19
17
17
21
25
19
21
23
19
23
15
17
19
19
22
18
20
18
21
19
18
18
15
16
22
17
17
18
13
16
19
16
15
16
18
16
15
17
15
18
18
20
...

result:

ok 66269 lines

Test #6:

score: 0
Accepted
time: 407ms
memory: 4288kb

input:

12796 185791
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...

output:

12100
7532
12357
12774
211
12761
5309
1646
12726
1882
247
118
1660
12229
12143
1499
1368
1273
1387
341
274
1374
1237
1359
112
1152
981
12681
949
890
820
774
62
644
836
925
12
13
1203
666
732
731
1127
12320
11473
82
655
12788
569
5866
621
2798
12114
85
609
11827
1
12455
56
605
575
530
54
645
1845
93
...

result:

ok 3210 lines

Test #7:

score: 0
Accepted
time: 457ms
memory: 3956kb

input:

16122 194030
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...

output:

9730
7096
4371
4171
3732
3716
3273
2910
2530
2423
2366
2351
2013
2196
2430
1891
1833
1852
1638
1709
1762
1699
1423
1295
1471
1255
1356
1428
1214
1191
1066
1104
1131
1116
1010
860
964
949
927
994
879
829
718
787
786
754
757
795
820
739
761
689
659
658
587
663
654
658
631
593
633
583
575
598
554
579
4...

result:

ok 9701 lines

Test #8:

score: 0
Accepted
time: 395ms
memory: 4512kb

input:

19492 191214
1 1 1 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 1 2 10 10 1 2 2 1 1 1 1 2 1 2 2 4 3 1 1 4 10 2 5 6 1 1 6 11 3 7 1 6 5 4 8 8 12 2 4 5 6 1 2 4 10 4 8 15 3 1 15 1 1 4 9 6 9 2 2 11 3 6 11 17 6 6 2 5 10 8 3 3 4 2 1 3 3 12 1 14 1 1 6 1 5 7 23 7 12 8 13 1 11 13 6 22 3 20 2 8 4 1 41 5 3 27 13 15 4 4 6 9 ...

output:

207
284
264
237
41
207
17559
198
186
201
168
1
1461
9
218
170
156
191
7
195
189
177
165
18623
170
25
151
18433
168
181
164
179
188
18572
1
171
172
182
137
179
184
127
162
166
167
171
17
147
180
165
175
173
167
1359
20
161
138
175
169
176
178
6
152
178
7
121
16
12
4
9
8
5
4
6
29
6
7
10
42
5
3
1
5
27
...

result:

ok 18556 lines

Test #9:

score: 0
Accepted
time: 432ms
memory: 4212kb

input:

22808 195820
1 1 1 1 1 1 1 1 1 1 2 2 1 1 2 2 1 1 3 2 1 2 4 4 1 2 1 5 4 1 4 2 1 3 1 1 3 1 4 3 4 5 15 1 6 10 1 1 3 1 1 1 1 3 5 7 4 2 3 15 4 4 1 11 1 2 5 2 2 12 4 3 1 9 6 4 2 1 3 5 5 1 4 1 2 16 15 1 6 1 10 1 9 6 9 2 1 12 6 2 13 2 3 1 8 17 2 8 1 16 5 28 4 24 2 9 5 1 11 18 15 6 7 10 3 1 1 11 8 1 12 4 7 1...

output:

42
45
42
45
40
47
43
37
38
41
37
44
42
38
42
34
34
32
37
37
37
39
35
45
35
40
32
36
43
34
33
39
29
32
33
33
33
31
28
32
35
31
23
33
31
30
26
34
28
30
35
32
32
30
33
28
26
29
30
26
24
27
25
28
22
30
26
27
23
29
31
25
27
30
26
26
33
30
27
26
21
32
27
28
28
25
31
26
24
24
24
23
30
22
26
21
26
27
24
22
...

result:

ok 39164 lines

Test #10:

score: 0
Accepted
time: 387ms
memory: 4356kb

input:

26352 183295
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 1 2 1 1 1 1 1 2 2 1 1 1 2 11 1 2 1 4 1 2 3 1 3 3 4 2 3 2 5 3 2 1 2 1 3 6 1 2 3 1 6 3 2 4 3 1 7 3 6 3 10 1 1 2 5 1 1 7 3 2 3 3 8 7 2 5 9 2 3 1 9 3 1 2 8 7 5 1 2 1 1 11 5 2 3 8 3 7 4 1 6 5 1 10 16 11 3 4 3 6 14 4 3 15 27 14 2 3 5 6 14 15 11 21 2 3 2 1...

output:

25212
25
316
497
330
4
314
304
24633
297
285
5
252
26284
11
256
281
275
26265
12
1
14
17
12
6
12
5
10
3
15
9
7
10
1
1
9
9
3
40
11
10
19
9
9
9
14
4
17
3
8
13
5
6
9
32
12
6
4
6
3
4
4
1
4
1991
29
40
1
5
30
911
3
9
11
44
45
3
1
15
1
16
9
16
14
3
15
31
15
1
7
14
367
3479
5
4
14
6
25
13
4
7
3
5
14
18
8
13...

result:

ok 3811 lines

Test #11:

score: 0
Accepted
time: 458ms
memory: 4020kb

input:

27196 199560
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 3 2 4 1 1 2 4 1 2 1 2 5 3 5 4 1 1 2 4 1 2 11 4 2 7 1 1 3 1 1 2 2 5 2 2 6 1 3 3 2 4 7 2 5 3 2 6 10 4 2 6 3 2 1 2 2 17 1 1 2 5 9 5 4 19 12 2 12 3 2 19 4 4 12 7 6 5 9 3 2 6 3 13 1 1 11 9 6 14 9 3 3 4 17 6 1 5 13 3 1 32 15 26 3 1 2 15 3 1 4 14 2 7 2 1...

output:

82
78
77
73
75
72
69
68
65
65
63
59
65
60
65
71
58
67
64
64
62
61
62
67
46
61
54
60
56
55
51
52
45
47
54
51
49
45
53
45
53
46
43
41
42
51
48
48
43
40
44
45
42
47
43
40
42
51
44
44
42
44
43
39
43
42
40
41
44
41
39
41
39
42
36
41
42
38
42
38
42
42
44
40
44
45
35
37
38
38
40
37
38
42
42
41
35
40
39
37
...

result:

ok 19956 lines

Test #12:

score: 0
Accepted
time: 445ms
memory: 4504kb

input:

32698 192710
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...

output:

32631
1529
1
1074
3158
151
32359
5093
4935
1295
32642
3805
365
3196
3342
2990
3159
3152
30578
509
2975
3034
32641
2753
7381
8616
2802
2351
32349
358
101
385
1998
8785
1
1959
5152
1923
1899
1763
395
1800
31873
1708
1729
185
1678
1507
1740
1591
1498
1633
102
1461
32109
1355
591
32295
1441
32692
146
53...

result:

ok 246 lines

Test #13:

score: 0
Accepted
time: 436ms
memory: 3788kb

input:

35920 186806
1 1 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 4 1 4 3 2 1 1 4 3 2 5 2 1 2 2 3 8 5 1 1 9 1 6 8 1 3 4 4 8 2 8 4 11 4 4 3 1 15 8 3 9 8 1 2 3 4 4 4 2 3 3 1 3 1 6 11 8 3 9 4 4 11 13 6 2 2 10 9 10 1 1 1 15 4 1 7 5 5 2 8 20 16 2 15 1 8 5 2 6 4 3 13 11 3 3 4 1 16 1 2 7 2 4 18 12 3 4 4 37 7 12 21 2 27 15 ...

output:

109
105
104
101
102
97
103
99
93
96
99
100
88
87
90
90
84
88
96
78
95
85
88
86
91
86
77
87
80
88
80
75
76
81
73
76
82
81
81
76
78
72
82
72
80
66
66
75
68
61
81
75
69
72
74
66
71
60
60
70
59
71
67
59
69
60
54
67
57
60
59
64
68
69
58
56
60
52
58
66
56
62
63
56
56
62
56
62
52
58
58
51
49
62
51
58
54
53...

result:

ok 15567 lines

Test #14:

score: 0
Accepted
time: 394ms
memory: 4672kb

input:

39372 196317
1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 1 1 1 3 1 3 2 2 1 1 1 4 4 3 6 1 2 1 5 4 7 2 5 1 2 2 5 2 12 2 7 7 2 5 6 14 2 5 4 6 2 8 14 2 3 4 8 12 1 2 5 3 1 10 6 8 3 4 4 8 13 2 2 6 14 12 4 3 29 8 2 1 39 2 15 9 17 1 7 18 1 5 2 9 6 7 1 6 10 3 14 10 35 12 4 17 2 2 3 11 6 7 2 6 12 12 9 9 6 4 22 5 7 5 26 5 5...

output:

36323
444
26954
457
83
38918
85
36668
383
362
1535
35763
51
339
301
38085
49
327
291
269
34799
278
34
11
31977
297
297
261
288
38187
42
286
37406
11131
293
1495
288
38036
268
8
627
235
3191
245
232
37103
272
264
23
34
271
2433
242
269
86
263
5
239
214
4
241
230
233
34576
237
34789
260
232
36453
3710...

result:

ok 76 lines

Test #15:

score: 0
Accepted
time: 405ms
memory: 4092kb

input:

32241 199734
1 1 1 1 2 2 2 1 1 2 1 1 1 3 2 2 1 1 2 1 1 2 1 3 2 1 1 4 1 1 6 3 1 1 1 6 1 9 7 5 2 1 7 2 4 1 1 5 5 3 3 5 5 5 1 1 1 2 2 2 2 9 7 3 7 7 10 3 6 4 4 3 2 4 5 1 3 1 4 6 1 15 1 1 1 2 17 8 12 3 2 3 6 9 7 5 1 3 12 17 2 5 15 2 3 3 12 7 4 35 8 9 5 4 18 5 10 8 26 13 2 2 1 15 6 2 3 1 19 2 8 8 3 11 13 ...

output:

34
31
29
34
26
32
28
24
31
31
32
30
29
28
26
29
27
24
26
28
32
30
31
23
28
28
25
32
22
23
27
28
29
29
31
29
27
27
31
26
32
26
27
28
28
28
24
23
29
25
21
22
22
26
27
24
25
27
23
22
26
22
21
23
26
23
23
24
22
19
28
22
25
19
23
20
27
24
24
22
24
26
21
21
23
23
20
25
21
27
21
21
26
22
22
21
22
23
24
29
...

result:

ok 66578 lines

Test #16:

score: -100
Runtime Error

input:

44885 197554
1 1 1 1 1 1 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 6 1 5 7 3 4 3 3 2 4 2 2 2 3 2 4 2 1 2 1 2 1 10 2 1 17 1 4 1 9 1 19 2 14 4 2 3 8 3 2 3 2 2 6 1 1 6 13 8 4 2 7 13 1 19 1 21 9 6 3 2 1 5 5 1 6 1 1 4 14 2 18 5 11 3 6 5 2 6 2 2 19 9 8 14 2 5 9 18 11 10 1 6 7 12 8 14 7 6 20 1 1 4 14...

output:


result: