QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78412#5403. 树数术541foreverCompile Error//C++204.2kb2023-02-18 19:19:502023-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]
  • 评测
  • [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;
}

Details

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]);
      |                                               ^~~