QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#660186 | #7626. Quake and Rebuild | nhuang685 | WA | 614ms | 3652kb | C++23 | 4.5kb | 2024-10-20 08:50:01 | 2024-10-20 08:50:01 |
Judging History
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';
}
}
}
詳細信息
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'