QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660186#7626. Quake and Rebuildnhuang685WA 614ms3652kbC++234.5kb2024-10-20 08:50:012024-10-20 08:50:01

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-10-20 08:50:01]
  • 评测
  • 测评结果:WA
  • 用时:614ms
  • 内存:3652kb
  • [2024-10-20 08:50:01]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-10-19 17:11:02
 *
 *
 */
#include <algorithm>

#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) {
    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';
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3536kb

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: -100
Wrong Answer
time: 614ms
memory: 3652kb

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
79
73
62
60
55
61
57
52
52
51
52
55
51
51
56
55
53
49
55
49
50
53
49
49
48
49
48
53
49
50
54
47
52
46
50
49
46
47
47
49
50
47
49
47
48
47
49
48
50
48
49
47
47
49
47
51
48
48
45
45
46
50
49
49
48
49
46
46
47
46
47
48
47
49
46
46
47
46
47
46
45
47
48
49
49
48
48
47
49
47
46
47
49
46
47
47
50
46
47
...

result:

wrong answer 2nd lines differ - expected: '78', found: '79'