再次垫底$\text{.jpg}$

$\text{score：20 + 0 + 10 = 30 rk：27/29}$

Problem A：sign

题面

题解

这题贼水，但我没想出来。。

我大概以为这不是数学所以没想到代入，或者是我忘记该点值表示可以 $O (\log A)$

反正全村就我没到及格线

题解懒得写了，就搬出题人给的吧

事实上，这个做法不能通过。

考虑上面做法复杂度瓶颈是快速幂。一个简单的$\text{trick}$是对于一个固定的 $son_u = k$，令 $M = \lceil \sqrt{A} \rceil$，预处理出 $k^0, k^1, k^2, …, k^{M - 1}$ 以及 $(k^M)^0, (k^M)^1, …, (k^M)^{M - 1}$。这样单次求某个点值就可以用 $O (1)$ 次算术运算求得。

时间复杂度为 $O ((n + \sqrt{A})\sqrt{n})$。

以上是出题人提供题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 998244353

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 5;

const int M = 1e04;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

struct LFS { int to, next; } ;
LFS Link[MAXN << 1];
int Head[MAXN]= {0}, size = 0;
void Insert (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N;
int a[MAXN]= {0}, son[MAXN]= {0};
int b[MAXN]= {0}, m = 0;
LL ans[MAXN]= {0};
LL inv;
LL f1[MAXN]= {0}, f2[MAXN]= {0};
inline LL calc (int p) {
	int base = p / M, rest = p - base * M;
	return f2[base] * f1[rest] % MOD;
}
LL work (int root, int t) {
	LL r;
	if (t == 1) r = a[root] + 1;
	else r = (1 - calc (a[root] + 1) + MOD) % MOD * inv % MOD;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		r = r * work (v, t) % MOD;
	}
	if (t == son[root]) ans[root] = r;
	return r;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum ();
	for (int i = 2; i <= N; i ++) {
		int fa = getnum ();
		Insert (fa, i); son[fa] ++;
	}
	for (int i = 1; i <= N; i ++) a[i] = getnum ();
	for (int i = 1; i <= N; i ++) b[++ m] = son[i];
	sort (b + 1, b + m + 1);
	m = unique (b + 1, b + m + 1) - b - 1;
	for (int i = 1; i <= m; i ++) {
		inv = power (1 - b[i] + MOD, MOD - 2);
		f1[0] = 1, f2[0] = 1;
		for (int j = 1; j <= M; j ++) f1[j] = f1[j - 1] * b[i] % MOD;
		for (int j = 1; j <= M; j ++) f2[j] = f2[j - 1] * f1[M] % MOD;
		work (1, b[i]);
	}
	for (int i = 1; i <= N; i ++) printf ("%lld\n", ans[i]);

	return 0;
}

Problem B：match

Problem C：tree

题面

题解

这题最基本的思路我一开始想了一下，然后马上扔了。。

首先考虑每个点它能够作为被 $LCA$ 的情况

考虑重链剖分，启发式合并，设点 $u$ 重子树 $A$，另一子树 $B$，则对 $i \in B, j \in A$，满足 $LCA (i, j) = u$，此时选择 $i, j$，$u$ 可以贡献给区间 $[l, r]$ 满足 $l \in [1, i], r \in [j, n]$（假定 $i < j)$，也就是说，极限情况即是取 $i$ 在 $A$ 中的前驱 $pre$ 与后继 $nxt$，则最大 $u$ 可贡献区间即为 $[1, pre] \cup [i, n]$ 与 $[1, i] \cup [nxt, n]$

此时不妨把区间 $l, r$ 视为二维平面上的点 $(l, r)$，那么上面所说的 $i$ 导致的 $u$ 的最大可贡献区间在平面上则投影为矩形 $(1, i), (1, n), (pre, i), (pre, n)$ 与矩形 $(1, nxt), (1, n), (i, nxt), (i, n)$（取矩形的四个角）

考虑把所有 $depth$ 一致的点所贡献的矩形涂上相同的颜色，求每种颜色的矩形各自的并，那么最终询问点 $(l, r)$ 被多少种颜色的面积所覆盖则是答案

求矩形的并也很简单，因为这些矩形都是严格贴着平面左上角（即 $(1, n)$）的

然后扫描线一波就做完了

不过不要忘了题面所说的 $i, j$ 可以相同，所以对每个 $i, i \in [1, n]$，还得加上 $(1, i), (1, n), (i, i), (i, n)$ 的矩形

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 5e05 + 10;

struct LFS { int to, w, next; } ;
LFS Link[MAXN << 1];
int Head[MAXN]= {0}, size = 0;
void Insert (int u, int v, int w) {
	Link[++ size].to = v;
	Link[size].w = w;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N, M;

int son[MAXN]= {0}, subsize[MAXN]= {0};
int d[MAXN]= {0};
LL dist[MAXN]= {0}, mpp[MAXN]= {0}, m = 0;
void DFS (int root, int father) {
	subsize[root] = 1;
	mpp[++ m] = dist[root];
	son[root] = - 1;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to, w = Link[i].w;
		if (v == father) continue;
		dist[v] = dist[root] + w;
		DFS (v, root);
		subsize[root] += subsize[v];
		if (son[root] == - 1 || subsize[v] > subsize[son[root]])
			son[root] = v;
	}
}
vector<pair<int, int> > mat[MAXN]; // <纵坐标, 横坐标>
set<int> st[MAXN];
set<int> :: iterator it, it2;
int ext[MAXN]= {0};
void merge (int x, int y, int id) {
	for (it = st[y].begin(); it != st[y].end(); it ++) {
		int i = * it;
		it2 = st[x].lower_bound(i);
		int pre = i, nxt = i;
		if (it2 != st[x].begin()) { it2 --; pre = * it2; }
		it2 = st[x].upper_bound(i);
		if (it2 != st[x].end()) nxt = * it2;
		if (nxt != i) mat[id].push_back(make_pair (nxt, i));
		if (pre != i) mat[id].push_back(make_pair (i, pre));
	}
	for (it = st[y].begin(); it != st[y].end(); it ++) st[x].insert(* it);
}
void make (int root, int father) {
	if (son[root] == - 1) {
		st[root].insert(root); ext[root] = root;
		return ;
	}
	make (son[root], root);
	ext[root] = ext[son[root]];
	st[ext[root]].insert(root);
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father || v == son[root]) continue;
		make (v, root);
		merge (ext[root], ext[v], d[root]);
	}
}
struct node {
	int x, y, type, id;
	// type: - 1, + 1, 2(dot)
	node (int x = 0, int y = 0, int type = 0, int id = 0) : x (x), y (y), type (type), id (id) {}
	bool operator < (const node& p) const {
		if (x == p.x) return type < p.type;
		return x < p.x;
	}
} ;
node a[MAXM << 2];
int n = 0;
void mesh (int id) {
	sort (mat[id].begin(), mat[id].end());
	int lx = 1;
	for (int i = 0; i < (int) mat[id].size(); i ++) {
		int y = mat[id][i].first, x = mat[id][i].second;
		if (x >= lx) {
			a[++ n] = node (lx, y, 1, id);
			a[++ n] = node (x + 1, y, - 1, id);
			lx = x + 1;
		}
	}
}
int answer[MAXM]= {0};
inline int lowbit (int x) { return x & (- x); }
int subsum[MAXN]= {0};
void add (int x, int delta) {
	while (x <= N) {
		subsum[x] += delta;
		x += lowbit (x);
	}
}
int query (int x) {
	int ret = 0;
	while (x > 0) {
		ret += subsum[x];
		x -= lowbit (x);
	}
	return ret;
}
void solve () {
	sort (a + 1, a + n + 1);
	for (int i = 1; i <= n; i ++) {
		int y = a[i].y, type = a[i].type, id = a[i].id;
		if (type == 2) answer[id] = query (y);
		else add (y, type);
	}
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	bool isneg = false;
	while (! isdigit (ch)) {
		if (ch == '-') isneg = true;
		ch = getchar ();
	}
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return isneg ? - num : num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i < N; i ++) {
		int u = getnum (), v = getnum (), w = getnum ();
		Insert (u, v, w), Insert (v, u, w);
	}
	DFS (1, 0);
	sort (mpp + 1, mpp + m + 1);
	m = unique (mpp + 1, mpp + m + 1) - mpp - 1;
	for (int i = 1; i <= N; i ++) d[i] = lower_bound (mpp + 1, mpp + m + 1, dist[i]) - mpp;
	for (int i = 1; i <= N; i ++) mat[d[i]].push_back(make_pair (i, i));
	make (1, 0);
	for (int i = 1; i <= m; i ++) mesh (i);
	for (int q = 1; q <= M; q ++) {
		int l = getnum (), r = getnum ();
		a[++ n] = node (l, r, 2, q);
	}
	solve ();
	for (int i = 1; i <= M; i ++) printf ("%d\n", answer[i]);

	return 0;
}