QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78410#5403. 树数术541forever0 1819ms276376kbC++204.1kb2023-02-18 19:16:522023-02-18 19:16:54

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:16:54]
  • 评测
  • 测评结果:0
  • 用时:1819ms
  • 内存:276376kb
  • [2023-02-18 19:16:52]
  • 提交

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%