QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#78410 | #5403. 树数术 | 541forever | 0 | 1819ms | 276376kb | C++20 | 4.1kb | 2023-02-18 19:16:52 | 2023-02-18 19:16:54 |
Judging History
answer
#include <bits/stdc++.h>
struct Tree {
const int n;
std::vector<std::vector<int>> e, st;
std::vector<int> rnk, dfn, lg, rdfn;
void DFS(int u, int fa) {
static int dfx = 0;
rnk[dfn[u] = ++dfx] = u;
for (auto v : e[u])
if (v != fa) {
DFS(v, u);
rnk[++dfx] = u;
}
rdfn[u] = dfx;
}
int Min(int x, int y) {
return dfn[x] < dfn[y] ? x : y;
}
Tree(int n) : n(n), e(n), st(std::__lg(n << 1) + 1, std::vector<int>(n << 1 | 1)), rnk(n << 1 | 1), dfn(n), lg(n << 1 | 1, -1), rdfn(n, 1) {
for (int i = 1, u, v; i < n; ++i) {
std::cin >> u >> v;
--u, --v;
e[u].emplace_back(v);
e[v].emplace_back(u);
}
DFS(0, -1);
for (int i = 1; i <= (n << 1); ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= (n << 1); ++i) st[0][i] = rnk[i];
for (int i = 1; i <= lg[(n << 1) - 1]; ++i)
for (int j = 1; j + (1 << i) - 1 <= (n << 1) - 1; ++j) {
st[i][j] = Min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
int LCA(int x, int y) {
if (x == -1) return y;
if (y == -1) return x;
x = dfn[x], y = dfn[y];
if (x > y) std::swap(x, y);
int l = lg[y - x + 1];
return Min(st[l][x], st[l][y - (1 << l) + 1]);
}
bool Sub(int x, int y) {
return dfn[x] <= dfn[y] && dfn[y] <= rdfn[x];
}
};
template<typename T>
class Fenwick {
const int n;
std::vector<T> a;
T _Sum(int x) {
T res = 0;
for (; x; x -= (x & (-x))) res += a[x];
return res;
}
public:
Fenwick(int n = 0) : n(n), a(n + 1) {}
void Add(int x, const T &v) {for (; x <= n; x += (x & (-x))) a[x] += v;}
T Sum(int l, int r) {return _Sum(r) - _Sum(l - 1);}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::vector<int>> e(n);
Tree T(n);
std::vector<int> a(m + 1), val(4 << std::__lg(m)), pre(m + 1);
for (int i = 1; i <= m; ++i) std::cin >> a[i], --a[i];
std::function<void(int, int, int)> Build = [&](int x, int l, int r) {
if (l == r) return val[x] = a[l], void();
int mid = (l + r) >> 1;
Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
val[x] = T.LCA(val[x << 1], val[x << 1 | 1]);
};
Build(1, 1, m);
auto Get = [m](int l, int r) {
std::vector<std::tuple<int, int, int>> ans;
std::function<void(int, int, int, int, int)> Split = [&](int x, int l, int r, int L, int R) {
if (l > R || L > r) return;
if (L <= l && r <= R) return ans.emplace_back(x, l, r), void();
int mid = (l + r) >> 1;
Split(x << 1, l, mid, L, R), Split(x << 1 | 1, mid + 1, r, L, R);
};
Split(1, 1, m, l, r);
return ans;
};
for (int i = 1; i <= m; ++i) {
auto cur = Get(1, i);
std::reverse(cur.begin(), cur.end());
int u = -1;
for (auto [x, l, r] : cur) {
if (T.Sub(a[i], T.LCA(val[x], u))) u = T.LCA(val[x], u), pre[i] = l;
else {
while (l < r) {
if (T.Sub(a[i], T.LCA(u, val[x << 1 | 1]))) {
x <<= 1;
r = (l + r) >> 1;
pre[i]=r+1;
u = T.LCA(u, val[x << 1 | 1]);
} else {
l = ((l + r) >> 1) + 1;
x = x << 1 | 1;
}
}
break;
}
}
}
std::vector<long long> ans(q, 0);
std::vector<std::vector<std::pair<int, int>>> Q(m + 1);
for (int k, i = 0; i < q; ++i) {
std::cin >> k;
int u = -1;
for (int L, R; k--;) {
std::cin >> L >> R;
int pt=L;
u = a[pt++];
auto cur = Get(L, R);
int v = -1;
for (auto [x, l, r] : cur) {
if (!T.Sub(T.LCA(v, val[x]), u)) v = T.LCA(v, val[x]), pt = r + 1;
else {
while (l < r) {
if (!T.Sub(T.LCA(v, val[x << 1]), u)) {
x = x << 1 | 1;
l = ((l + r) >> 1) + 1;
v = T.LCA(v, val[x << 1]);
} else {
x <<= 1;
r = (l + r) >> 1;
}
}
assert(l==r);
pt = l;
break;
}
}
for (auto [x, l, r] : cur) u = T.LCA(u, val[x]);
Q[pt - 1].emplace_back(L, q + i);
Q[R].emplace_back(L, i);
}
}
Fenwick<long long> bit(m);
for (int i = 1; i <= m; ++i) {
bit.Add(pre[i], 1);
for (auto [L, id] : Q[i])
id >= q ? ans[id - q] -= bit.Sum(1, L) : ans[id] += bit.Sum(1, L);
}
for (auto c : ans) std::cout << c << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1804ms
memory: 276376kb
input:
699990 699995 233333 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50...
output:
588002 909117 733100 572654 924068 486375 401975 454211 664664 825374 444411 404737 419831 163975 659087 216139 487932 16634 324179 27351 103756 221493 317391 981489 339876 150935 180087 229206 198892 571129 805009 422883 389557 529102 895742 93773 1265342 559353 62365 222331 892852 318614 429060 29...
result:
wrong answer 1st lines differ - expected: '121987', found: '588002'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 1819ms
memory: 266892kb
input:
699992 699994 699992 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 29 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 40 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 ...
output:
211594 160846 176729 128251 32662 70710 74884 9095 68282 91324 154262 24279 31878 173468 75265 139715 91660 87525 194302 16875 81535 172911 29145 20483 151883 5255 9548 58890 38076 94152 14358 74859 48870 23981 41390 60976 13795 125823 427 26641 130620 174231 73241 55291 2364 78864 23391 4866 36002 ...
result:
wrong answer 199th lines differ - expected: '14838', found: '14837'
Subtask #3:
score: 0
Wrong Answer
Test #3:
score: 0
Wrong Answer
time: 190ms
memory: 37792kb
input:
99998 99993 33333 2 1 3 1 4 3 5 3 6 5 7 5 8 7 9 7 10 9 11 9 12 11 13 11 14 13 15 13 16 15 17 15 18 17 19 17 20 19 21 19 22 21 23 21 24 23 25 23 26 25 27 25 28 27 29 27 30 29 31 24 32 31 33 31 34 33 35 33 36 35 37 35 38 37 39 37 40 39 41 39 42 41 43 41 44 43 45 43 46 45 47 45 48 47 49 47 50 49 51 49 ...
output:
9733 11330 8406 5136 22208 23231 12687 27289 23742 20945 18158 16380 8991 14038 11672 14685 20275 18955 21685 7937 21383 23578 14838 5714 15707 10015 7907 13254 13883 10446 16141 16796 11009 11913 15761 20419 11157 12192 14327 18263 19103 5239 4114 16529 7413 5006 16845 8747 19380 22601 12023 9163 9...
result:
wrong answer 3rd lines differ - expected: '8403', found: '8406'
Subtask #4:
score: 0
Skipped
Dependency #1:
0%