晚了几天写，暴力场

$\text{score：40 + 40 + 45 = 125 rk：17/30}$

Problem A：Tree

题目描述

数据范围

对 $100\%$ 的数据，$1 \le n \le 10^8, ~ 1000 \le k \le 10^8$

题解

很容易发现，满足条件等价于要求树中没有任意一条从根出发的路径经过超过 $k - 1$ 个左儿子

然后就是一个很妙的转换，将树按如下规则变为括号序列：

子树 $u$ 括号序 = ‘(‘ + ‘$u$ 左子树括号序’ + ‘)’ + ‘$u$ 右子树括号序

给个题解的图例

实际上可以不用考虑叶节点，那么现在将 $n$ 变为 $n - 1$，$k$ 变为 $k - 2$

那么现在的任务就变为在坐标系中将左括号看作往右上角走，右括号看作往右下角走，从 $(0, 0)$ 最终走到 $(2n, 0)$ 的方案数，并需要满足过程中纵坐标始终在 $[0, k]$ 中的方案数（注意此时 $n, k$ 已变化）

这就是类似卡特兰数，但是有两条限制，即不能碰到 $y = - 1$ 也不能碰到 $y = k + 1$

又从 $(x1, y1)$ 走到 $(x_2, y_2)$ 无限制的方案数为 $f(x_1, y_1, x_2, y_2) = \dbinom{|x_1 - x_2|}{\frac{|x_1 - x_2| + |y_1 - y_2|}{2}}$

考虑容斥，首先有总方案数 $f(0, 0, 2n, 0)$，再取对称一次、两次、三次。。求方案数

对称一次即对称到 $(0, -2), (0, 2k + 2)$，减去其到 $(2n, 0)$ 的方案数

对称两次分类讨论，先经过 $y = - 1$ 再经过 $y = k + 1$ 或先经过 $y = k + 1$ 再经过 $y = - 1$，对第一种情况，对称两次后到 $(0, 2k + 4)$，对第二种，到 $(0, - 2k - 4)$，再加上它们到 $(2n, 0)$ 的方案数

但是会发现这样会多加上对称三次的答案，所以还需减去对称三次中讨论的答案

举个例子，考虑上图这样一个运动轨迹，那么它一共会被这些所计算到：先下再上、先上再下、下上下、上下上、下上下上

实际上有应该作贡献的只有最后一个“下上下上”而已，所以是要容斥的

可以知道没两次对称就可以使纵坐标绝对值增加 $2k + 4$，当纵坐标绝对值超过 $2n$ 时，显然贡献为 $0$，此时就可以停止，那么计算总次数大约为 $\frac{4n}{k}$

时间复杂度 $O (\frac{n}k \log_p 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

#define MOD 10007

using namespace std;

const int MAXN = MOD + 10;

typedef long long LL;

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;
}

int N, K;

LL fact[MAXN]= {0}, invfact[MAXN]= {0};
inline LL C (int n, int m) {
	if (n < m) return 0;
	return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD;
}
inline LL lucas (int n, int m) {
	if (n == m) return 1;
	if (n < m) return 0;
	if (n <= MOD && m <= MOD) return C (n, m);
	return C (n % MOD, m % MOD) * lucas (n / MOD, m / MOD) % MOD;
}
int n, k;
inline int sym (int y, int p) { return p ? - y - 2 : - y + 2 * k + 2; } // y = - 1 & y = k + 1
inline LL path (int y) { return lucas (2 * n, n + y / 2); }

int main () {
	cin >> N >> K;
	n = N - 1, k = K - 2;
	fact[0] = invfact[0] = 1;
	for (int i = 1; i < MOD; i ++) fact[i] = fact[i - 1] * i % MOD;
	invfact[MOD - 1] = power (fact[MOD - 1], MOD - 2);
	for (int i = MOD - 2; i >= 1; i --) invfact[i] = invfact[i + 1] * (i + 1) % MOD;
	int up = 2 * k + 2, down = - 2, p = 1;
	LL ans = lucas (2 * n, n);
	while (true) {
		if (abs (up) > 2 * n && abs (down) > 2 * n) break;
		int t = p == 1 ? - 1 : 1;
		ans = (ans + t * path (up) % MOD + MOD) % MOD;
		ans = (ans + t * path (down) % MOD + MOD) % MOD;
		up = sym (up, p), down = sym (down, p ^ 1);
		p ^= 1;
	}
	cout << ans << endl;

	return 0;
}

Problem B：文本编辑器

Problem C：第k深(kth)

题目描述

一个 $n$ 个点的有根树，$1$ 为根，带边权，有 $m$ 次操作

  • 操作 $1$：求 $x$ 的子树中第 $k$ 小的深度的值，如果子树中没有 $k$ 个点则输出 $- 1$
  • 操作 $2$：将 $x$ 与 $x$ 父亲的边权加上 $k$

保证每次操作 $2$ 的 $k$ 以及原树的边权小于等于一个数 $len$
如果操作 $2$ 中 $x$ 为 $1$，那么视为将 $x$ 的基础深度加上了 $k$

数据范围

对 $100\%$ 的数据，$1 \le n, m \le 10^5, ~ 1 \le len \le 10, ~ k \in N^+$

题解

原题 少女与战车

$\text{lxl}$ 分块题。。

首先搞出每个点的 $DFS$ 序，那么每次修改就是区间加

现在考虑如何分块，据说这种分块方式可能叫双关键字分块？

对每一块，保证

  • 每一块最大（小）值 $max(min)$，块左右端点 $l, r$，满足，$max - min \le 2\sqrt{10m}$ 且 $r - l + 1 \le \sqrt n$

那么这样就可以保证块的分割点个数不超过 $\frac{10m}{\sqrt{10m}} + \frac{n}{\sqrt n}$

查询二分，然后在每个块内存块每个元素比块中最小值大多少，并记录它们的个数，那么每次 $check$ 的时候就可以 $O (1)$ 查询块内比 $mid$ 小的点的个数

然后每修改 $1000$ 重新分块，修改 $1000$ 次后块内最大最小值差不会新增超过 $20000$，这也是数组能存下的极限

代码

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 <cmath>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;
const int MAXB = 2000 + 10;
const int MAXV = 20000 + 10;

const int INF = 0x3f3f3f3f;
const LL LINF = 0x3f3f3f3f3f3f3f3f;
const int V = 2000;

struct LFS { int to, w, next; } ;
LFS Link[MAXM << 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, len;

int subsize[MAXN]= {0};
int dfn[MAXN]= {0}, ord = 0;
LL d[MAXN]= {0};
void DFS (int root, LL dist) {
	subsize[root] = 1;
	dfn[root] = ++ ord; d[ord] = dist;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to, w = Link[i].w;
		DFS (v, dist + w);
		subsize[root] += subsize[v];
	}
}

int lim;
int bel[MAXN]= {0}, bl[MAXB]= {0}, br[MAXB]= {0}, m = 0;
LL mini[MAXB]= {0}, maxi[MAXB]= {0};
int subsum[MAXB][MAXV]= {0}, lazy[MAXB]= {0};
void maintain (int i) {
	mini[i] = LINF, maxi[i] = - LINF;
	for (int j = bl[i]; j <= br[i]; j ++) {
		d[j] += lazy[i];
		mini[i] = min (mini[i], d[j]);
		maxi[i] = max (maxi[i], d[j]);
	}
	lazy[i] = 0;
	for (int j = 0; j <= maxi[i] - mini[i]; j ++) subsum[i][j] = 0;
	for (int j = bl[i]; j <= br[i]; j ++) subsum[i][d[j] - mini[i]] ++;
	for (int j = 1; j <= maxi[i] - mini[i]; j ++) subsum[i][j] += subsum[i][j - 1];
}
void pushdown (int p) {
	if (! lazy[p]) return ;
	for (int i = bl[p]; i <= br[p]; i ++) d[i] += lazy[p];
	lazy[p] = 0;
}
void build () {
	for (int i = 1; i <= m; i ++) pushdown (i);
	LL mi = LINF, ma = - LINF; m = 1;
	for (int i = 1; i <= N; i ++) {
		mi = min (mi, d[i]), ma = max (ma, d[i]);
		if (ma - mi > V || i - br[m - 1] > lim) {
			bl[m] = br[m - 1] + 1, br[m] = i - 1;
			mi = ma = d[i]; m ++;
		}
		bel[i] = m;
	}
	bl[m] = br[m - 1] + 1, br[m] = N;
	for (int i = 1; i <= m; i ++) maintain (i);
}
void modify (int l, int r, int x) {
	if (bel[l] + 1 >= bel[r]) {
		for (int i = l; i <= r; i ++) d[i] += x;
		maintain (bel[l]); maintain (bel[r]);
		return ;
	}
	for (int i = l; i <= br[bel[l]]; i ++) d[i] += x;
	maintain (bel[l]);
	for (int i = bel[l] + 1; i <= bel[r] - 1; i ++) { lazy[i] += x; mini[i] += x, maxi[i] += x; }
	for (int i = bl[bel[r]]; i <= r; i ++) d[i] += x;
	maintain (bel[r]);
}
bool check (int l, int r, int k, LL mid) {
	int cnt = 0;
	if (bel[l] + 1 >= bel[r]) {
		for (int i = l; i <= r; i ++) cnt += d[i] <= mid;
		return cnt >= k;
	}
	for (int i = l; i <= br[bel[l]]; i ++) cnt += d[i] <= mid;
	for (int i = bel[l] + 1; i <= bel[r] - 1; i ++)
		if (mid - mini[i] >= 0)
			cnt += subsum[i][min (maxi[i] - mini[i], mid - mini[i])];
	for (int i = bl[bel[r]]; i <= r; i ++) cnt += d[i] <= mid;
	return cnt >= k;
}
LL query (int l, int r, int k) {
	pushdown (bel[l]); pushdown (bel[r]);
	LL left = LINF, right = - LINF;
	for (int i = bel[l]; i <= bel[r]; i ++) {
		left = min (left, mini[i]);
		right = max (right, maxi[i]);
	}
	if (left == right) return left;
	LL ans = left;
	while (left <= right) {
		LL mid = (left + right) >> 1;
		if (check (l, r, k, mid)) { ans = mid; right = mid - 1; }
		else left = mid + 1;
	}
	return ans;
}

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 (), len = getnum ();
	lim = sqrt (N); 
	for (int i = 2; i <= N; i ++) {
		int fa = getnum (), w = getnum ();
		Insert (fa, i, w);
	}
	DFS (1, 0);
	int modi = 0;
	build ();
	for (int q = 1; q <= M; q ++) {
		int opt = getnum (), x = getnum (), k = getnum ();
		if (opt == 1) {
			if (subsize[x] < k) { puts ("-1"); continue; }
			printf ("%lld\n", query (dfn[x], dfn[x] + subsize[x] - 1, k));
		}
		else {
			modi ++;
			if (! (modi % 1000)) build ();
			modify (dfn[x], dfn[x] + subsize[x] - 1, k);
		}
	}

	return 0;
}