QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#78412 | #5403. 树数术 | 541forever | Compile Error | / | / | C++20 | 4.2kb | 2023-02-18 19:19:50 | 2023-02-18 19:19:50 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-02-18 19:19:50]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-02-18 19:19:50]
- 提交
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;
if(u==-1){
u = a[pt];
}else{
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;
}
詳細信息
answer.code: In function ‘int main()’: answer.code:141:47: error: ‘cur’ was not declared in this scope 141 | for (auto [x, l, r] : cur) u = T.LCA(u, val[x]); | ^~~