2019-2020 XX Open Cup Grand Prix of Korea 虚拟参赛 暨 补题

自闭训练

分组读题, 22min我过了签到题A.

1h2min蒋叶桢过另一个签到题G.

同时读完了所有题.

我做完A后想H, 张炀杰在想C, 蒋叶桢做完G后也开始想C.

H大致方向没错(转化为01序列, 逆序对), 可就是想不出来.

蒋叶桢C也卡了, 不会实现.

然后大家去想J, 不会.

时间一分一秒过去, 我们摸了3h的鱼. 最后1h, 大家都放弃了, 全员开始推箱子.

自闭 :(.

我太菜了, 净给队友拖后腿.

UPD(2020-11-5): H其实很简单, 当时可能是因为没有休息好, 脑子不在状态.

自闭, 不想补, 过几天再来

UPD 2020-11-5:

按难度排序(可能)

给出一个$n \times m$的"扑克牌"矩阵, 其中扑克牌只有"6", “7”, “8”, “9”.

可以旋转任意位置的扑克牌, 使扑克牌矩阵中心对称. 求最小旋转次数.

($6$与$9$中心对称, $8$与$8$中心对称, $7$只能和中心旋转后的$7$中心对称)

$1 \le n, m \le 500$

直接模拟即可, 判断$(i, j)$和$(n - i + 1, m - j + 1)$(中心对称位置)的牌是否可以通过旋转某一张来使得其对称. 注意中心点只有$8$可满足条件. 详见代码.

复杂度$O(n^2)$

 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
const int maxn = 510;

int n, m, ans = 0;
char str[maxn][maxn];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%s", str[i] + 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int ii = n - i + 1, jj = m - j + 1;
			int a = str[i][j] - '0', b = str[ii][jj] - '0';
			if (i == ii && j == jj) {
				if (a != 8) {
					ans = -1;
					break;
				}
			}
			else {
				if (a == 6) {
					if (b == 6)
						ans++;
					else if (b != 9) {
						ans = -1;
						break;
					}
				}
				else if (a == 9) {
					if (b == 9)
						ans++;
					else if (b != 6) {
						ans = -1;
						break;
					}
				}
				else if (a == 8) {
					if (b != 8) {
						ans = -1;
						break;
					}
				}
				else if (a == 7) {
					if (b != 7) {
						ans = -1;
						break;
					}
					else
						ans++;
				}
			}
		}
		if (ans == -1)
			break;
	}
	if (ans == -1)
		puts("-1");
	else
		printf("%d\n", ans/2);
	return 0;
}

背景是希尔伯特的旅馆问题.

一个旅馆有无限个房间, 从$0$开始编号, 一开始都住满了人, 这些人设为第$0$组. 随后会有其他旅客组团入住旅馆. 如果下一组有$k$个旅客入住, 那么原先住在$x$号房间的人移至$x+k$号房间, 空出$0$到$k-1$号房间给新入住的旅客; 如果下一组有无限个旅客入住, 那么原先住在$x$号房间的旅客移至$2x$号房间, 空出$2x+1$号房间给新入住的旅客.

$Q (1 \le Q \le 3 \cdot 10^5)$次操作:

  • 1 k $k \ne 0$时, 有$k$个旅客入住; $k = 0$时, 有无现个旅客入住. $0 \le k \le > 10^9$.
  • 2 g x 查询第$g$组旅客第$x$小房号模$10^9 + 7$. $1 \le x \le 10^9$, 保证存在解
  • 3 x 查询房号为$x$的房间住的是第几组的旅客. $0 \le x \le 10^9$

询问$2, 3$是独立的, 先看看$2$怎么做吧.

由于给定了组号, 并且各组之间也是独立的, 每组第$x$小的房间号是否可以用一个函数写出来呢? 答案显然是可以! 一开始第$0$组的函数为$g_0(x) = x$, 如果新来了$k_1$个旅客, 那么原来的函数都加上一个$k_1$, 比如$g_0(x)$变为$g_0(x) = x + k_1, (0 \le x)$, 新来的这一组函数为$g_1(x) = x, (0 \le x < k_1)$. 如果新来了无限个旅客, 那么原来的函数都乘以$2$, 比如$g_0(x) = 2x + 2k_1, (0 \le x)$, $g_1(x) = 2x, (0 \le x < k_1)$, 新来的这一组函数为$g_2(x) = 2x + 1, (0 \le x)$. 这样对于查询$2$, 就可以很方便地代值计算得到答案了.

结合题目和这些函数, 可以发现, 函数是一次函数. 又由于要对前缀进行区间修改, 可以考虑使用线段树, 那么找一个特定的组号就是单点查询. 进一步发现, 一次函数中, $x$的系数一定是$2$的次幂, 所以我们在保存节点信息时, 可以保存系数的指数, 以及截距. 答案需要取模, 所以截距可以取模保存. 因为是区间修改, 还需要打个lazy tag.

对于询问$3$, 先来考虑暴力的做法. 直接存哪个房价住的是哪些人是不现实的, 但是我们可以"回溯". 即给出的$x$, 去考虑上一个操作$1$, 如果是入住$k$个人, 那么这个查询就相当于没有上一个操作$1$, 然后查询3 (x-k). 当然如果$x-k$是负数, 那么显然这个$x$就是属于上一个操作$1$所修改的, 即答案为上一个操作$1$的组号. 入住无限个旅客也是同理, 让$x$除以$2$, 如果$x$是奇数, 那么就是属于上个操作$1$所修改的, 否则就可以看成在上一个操作$1$之前的查询3 x/2. 因为每个操作$1$, 对应每一组, 所以一直回溯, 便可找到相应的组了.

这样复杂度是$O(Q)$的, 加上查询就是$O(Q^2)$, 显然不行. 但是这个做法有优化的空间. 如果有一段连续的加$k$, 设他们的和为$sum$, 那么就可以直接$O(1)$判断答案是不是在这一段连续的加中. 即, 如果$x’ = x - sum < 0$, 则在, 否则不在. 在的话可以二分, $O(logQ)$找到具体是哪一个点让他小于$0$. 不在的话, 说明需要再往前找. 连续一段加的前面一个是乘以$2$, 那么首先看$x’$的奇偶性, 像之前说的那样判断是找到了还是需要继续回溯.

记录乘以$2$出现的位置, 即可直接找到一段连续的加(见代码p2[]).

维护一段连续的加, 需要的是后缀和. 其实可以在操作的过程中$O(Q)$维护前缀和$pre[]$, 后缀和可以通过两个前缀和的差得到.

这样查询$3$的复杂度就只和乘以$2$的次数有关. 每次到乘以$2$的点都会让$x$减半, 那么查询$3$的复杂度就是$O(logx + logQ)$

需要特别注意的是$x = 0$(或者在回溯的过程中$x’ = 0$)的情况. 如果此时前面都是乘以$2$的操作, 那么他会一直跑完这些操作, 这样复杂度会被卡成$O(Q^2)$, 所以我们需要特判$x = 0$(或$x’ = 0$)的情况: 对于连续的乘以$2$, 直接跳到最前面第一个乘以$2$的操作即可. 可$O(Q)$在过程中预处理(见代码last_2[], gid[]).

总复杂度$O(Q(logQ + logx)) \approx O(QlogQ)$

(过程中需要用到G-1, 所以我的G从$1$开始; 第$x$小是直接代入, 所以$x-1$, 当然也可以初始化一次函数截距b为$10^9 + 6$, $x$直接代入)

  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
const int maxn = 3e5+10;
const int P = 1e9+7;

int Plus(LL a, LL b) {
	return a + b >= P ? (a + b) % P : a + b;
}

int Mult(LL a, LL b) {
	return a * b >= P ? a * b % P : a * b;
}

struct SegmentTreeNode {
	int l, r, mid, pk, b;
} tree[maxn << 2];

int n, pw[maxn], G = 1, last_2[maxn], cnt = 0, gid[maxn];
LL pre[maxn];
vector<int> p2;

void Build(int v, int l, int r) {
	tree[v] = SegmentTreeNode{l, r, (l+r)>>1, 0, 0};
	if (l == r)
		return;
	else {
		Build(LCH(v), l, tree[v].mid);
		Build(RCH(v), tree[v].mid+1, tree[v].r);
	}
}

void Init() {
	pw[0] = 1;
	for (int i = 1; i <= n; i++)
		pw[i] = Mult(pw[i-1], 2);
	Build(1, 1, n);
}

void UpdateNode(int v, int pk, int b) {
	tree[v].b = Mult(pw[pk], tree[v].b);
	tree[v].b = Plus(tree[v].b, b);
	tree[v].pk += pk;
}

void Down(int v) {
	UpdateNode(LCH(v), tree[v].pk, tree[v].b);
	UpdateNode(RCH(v), tree[v].pk, tree[v].b);
	tree[v].pk = tree[v].b = 0;
}

void Update(int v, int l, int r, int pk, int b) {
	if (tree[v].l == l && tree[v].r == r)
		UpdateNode(v, pk, b);
	else {
		Down(v);
		if (l > tree[v].mid)
			Update(RCH(v), l, r, pk, b);
		else if (r <= tree[v].mid)
			Update(LCH(v), l, r, pk, b);
		else {
			Update(LCH(v), l, tree[v].mid, pk, b);
			Update(RCH(v), tree[v].mid+1, r, pk, b);
		}
	}
}

int Query(int v, int p, int x) {
	if (tree[v].l == tree[v].r)
		return Plus(Mult(pw[tree[v].pk], x), tree[v].b);
	Down(v);
	if (p > tree[v].mid)
		return Query(RCH(v), p, x);
	else
		return Query(LCH(v), p, x);
}

int main() {
	scanf("%d", &n);
	Init();
	pre[1] = 0;
	last_2[1] = -1;
	for (int i = 1; i <= n; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1){
			int k;
			scanf("%d", &k);
			if (k) {
				Update(1, 1, G++, 0, k);
				pre[G] = pre[G-1] + k;
				last_2[G] = 0;
			}
			else {
				Update(1, 1, G++, 1, 0);
				Update(1, G, G, 1, 1);
				pre[G] = 0;
				last_2[G] = last_2[G-1] ? last_2[G-1] : G;
				gid[G] = cnt++;
				p2.push_back(G);
			}
		}
		else if (op == 2){
			int g, x;
			scanf("%d%d", &g, &x);
			printf("%d\n", Query(1, g+1, x-1));
		}
		//下面写的和狗屎一样丑, 能力有限, 见谅
		else {
			int x;
			scanf("%d", &x);
			int cur = G, res = 1, L = 2, R = G, flag = 1;
			for (int i = p2.size() - 1; ~i; i--) {
				// 等于0也可回溯上一步
				if (x - pre[cur] >= 0) {
					x -= pre[cur];
					if (x & 1) {
						res = p2[i];
						flag = 0;
						break;
					}
					else {
						if (x == 0) {
							cur = last_2[p2[i]];
							i = gid[cur];
						}
						x >>= 1;
						cur = p2[i] - 1;
						R = cur;
					}
				}
				else {
					L = p2[i] + 1, R = cur;
					break;
				}
			}
			if (flag) {
				while (L <= R) {
					int mid = (L + R) >> 1;
					if (x - (pre[cur] - pre[mid-1]) < 0) {
						L = mid + 1;
						res = mid;
					}
					else
						R = mid - 1;
				}
			}
			printf("%d\n", res-1);
		}
	}
	return 0;
}

给出一张$n$个点$m$条边的有向图, 边权为互不相等的正整数. 找一条$s$到$t$的路, 使得路上边权依次组成的数组字典序最小.

如果路无限长, 输出"TOO LONG"

如果不存在$s$到$t$的路, 输出"IMPOSSIBLE"

$1 \le n \le 10^5, 0 \le m \le 3 \cdot 10^5$

显然贪心.

但直接贪心可能会走到某个不通向$t$的点, 然后跑不到$t$. 但其实可以跑其他路到$t$.

为了避免这样的情况, 需要找一个子图, 保证子图上的每一条边都可以跑到$t$, 在子图上贪心即可.

如何寻找这样的子图? 先建一个"反图", 从$t$跑一遍, 记录能跑到的边, 这些边即是可以通向$t$的边.

然后依照这些边建立一张新的图, 边依据边权排序, 然后dfs第一条边即可.

注意有环就退出.

复杂度$O(n + mlogm)$

 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
const int maxn = 1e5+10;
const int maxm = 3e5+10;

int n, m, s, t, vis[maxn];
vector<int> G[maxm], G2[maxm], ans;

struct Edge {
	int u, v, c, flag;
} edges[maxm];

bool cmp( int i, int j) {
	return edges[i].c < edges[j].c;
}

void dfs(int v) {
	vis[v] = 1;
	for (auto i : G2[v]) {
		Edge &e = edges[i];
		e.flag = 1;
		if (!vis[e.u])
			dfs(e.u);
	}
}

bool dfs2(int u) {
	if (u == t)
		return true;
	vis[u] = 2;
	Edge &e = edges[G[u][0]];
	if (vis[e.v] == 2)
		return false;
	ans.push_back(e.c);
	return dfs2(e.v);
}

void Print() {
	for (auto x : ans)
		printf("%d ", x);
	puts("");
}

int main() {
	scanf("%d%d%d%d", &n, &m, &s, &t);
	for (int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		edges[i] = Edge{u, v, c, 0};
		G2[v].push_back(i);
	}
	dfs(t);
	for (int i = 1; i <= m; i++) {
		Edge &e = edges[i];
		if (e.flag) {
			G[e.u].push_back(i);
		}
	}
	if (!G[s].size())
		puts("IMPOSSIBLE");
	else {
		for (int i = 1; i <= n; i++)
			sort(G[i].begin(), G[i].end(), cmp);
		if (dfs2(s))
			Print();
		else
			puts("TOO LONG");
	}
	return 0;
}

给出长度为$n$的两个全排列$a, b$, 一次操作能交换$a$中两个相邻的元素, 求最小交换次数, 使得$\sum_{i=1}^n \mid a_i - b_i \mid$最大.

先来考虑$n$为偶数的情况. 要使得$\sum_{i=1}^n \mid a_i - b_i \mid$最大, 可以发现, $a, b$对应的元素$a_i, b_i$, 应该满足$a_i \le \frac{n}{2}, b_i > \frac{n}{2}$, 或者$a_i > \frac{n}{2}, b_i \le \frac{n}{2}$. 证明显然, 略(懒).

所以可以转化成$01$序列: $x \le \frac{n}{2}$的为$0$, 否则为$1$. 然后将$b$取反, 就得到了$a$的目标$a’$. “交换相邻元素"等价于求逆序对, 这个转化方法适用于所有序列, 包括有可重元素的数列, 当然包括$01$序列.

但是这里的$a’$不是按顺序排的, 所以直接求$a$的逆序对是不可行的.

下面有两种解决方法, 第一是构造一个最优的排列, 求逆序对.

将$a’$的下标数组$p_{a’}$取出, 按照贪心, 对$a$求一个排列$p$. 如:

$$ \begin{aligned} a = &\{1, 1, 0, 1, 0, 0\} \\ a’ = &\{0, 1, 0, 0, 1, 1\} \end{aligned} $$

$a’$的下标取出

$$ \begin{aligned} a’ = &\{0, 1, 0, 0, 1, 1\} \\ p_{a’} = &\{1, 2, 3, 4, 5, 6\} \end{aligned} $$

那么:

  • $a$的第一个数是$1$, 找到$a’$中第一个$1$的下标, 为$2$, 所以$p$的第一个元素为$2$;
  • $a$的第二个数是$1$, 找到$a’$中第二个$1$的下标, 为$5$, 所以$p$的第二个元素为$5$;
  • $a$的第二个数是$0$, 找到$a’$中第一个$0$的下标, 为$1$, 所以$p$的第二个元素为$1$

$\dots$

这样就得到了一个全排列$p$, 对$p$求逆序对, 即是交换次数.

奇数暂不讨论, 往下看有.

复杂度$O(nlogn)$

第二种方法:

只有$0$和$1$, 根据上述贪心方法, 可以发现, 其实我们是把$a$中第$i$个$1$和$a’$中第$i$个$1$“配对”. $0$同理.

简单证明一下:

不失一般性, 以$1$的配对为例. 如果不是这样, 那么在交换的过程中某一个$1$会"跨过"另一个$1$去配对, 被"跨过"的$1$位置已经改变, 如果改变以后朝着他的配对位置移动, 则答案不变; 如果朝着配对位置相反的方向移动, 则需要多移动一次, 不如直接让这个被跨过的$1$去配对当前$1$的配对位置.

证毕.

由于只有$01$序列, 我们只要把$1$配对了, $0$一定也是配对的. 并且这样的配对方式不会影响到其他$1$的移动次数, 所以我们只需要对每个一$1$, 计算他在两个数组中下标的差即可.

$n$是奇数的情况就很好考虑了. $\lceil \frac{n}{2} \rceil$既可以与小的配对, 也可以与大的配对, 因为和谁配对都不会改变答案. 所以我们让他分别是$1, 0$做两遍, 去最小答案即可.

复杂度$O(n)$

(没写$O(nlogn)$的傻子做法)

 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
const int maxn = 2.5e5 + 10;

int n, a[maxn], b[maxn];
LL ans;
vector<int> sa, sb;

LL sol() {
	LL res = 0;
	sa.clear();
	sb.clear();
	for (int i = 1; i <= n; i++) {
		if (a[i])
			sa.push_back(i);
		if (b[i])
			sb.push_back(i);
	}
	for (int i = 0; i < sa.size(); i++)
		res += llabs(sa[i] - sb[i]);
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	for (int i = 1; i <= n; i++)
		scanf("%d", b + i);
	if ((n&1) == 0) {
		for (int i = 1; i <= n; i++) {
			a[i] = (a[i] > n/2);
			b[i] = (b[i] <= n/2);
		}
		ans = sol();
	}
	else {
		int pa = -1, pb = -1;
		for (int i = 1; i <= n; i++) {
			if (a[i] == n/2 + 1)
				pa = i;
			if (b[i] == n/2 + 1)
				pb = i;
			a[i] = a[i] > n/2 + 1;
			b[i] = b[i] <= n/2;
		}
		a[pa] = 1, b[pb] = 1;
		ans = sol();
		a[pa] = 0, b[pb] = 0;
		ans = min(ans, sol());
	}
	printf("%lld\n", ans);
	return 0;
}

有一根长度为$10^6$的线段$[1, 10^6]$和$n$个小线段$[l_i, r_i]$, 他们要么有包含关系, 要么不相交(可以相接). 每个线段有一个权值$v_i$. 选择一些线段, 这些线段满足包含关系层次不超过$k$(即每一个点, 属于不超过$k$个小线段), 同时使选择的小线段的$\sum v_i$最大. 对于每个$k \in [1, n]$, 输出最大值.

$1 \le n \le 2.5 \cdot 10^5, 1 \le l, r \le 10^6, 1 \le v \le 10^9$

很自然地(zzs原话), 发现线段只有包含关系, 可以构成一棵树. 我们把最大的线段当成根, 权值为$0$即可. 由于需要对每个$k$都输出答案, 所以可以考虑dp.

先来看这样的一个状态: $dp(i, j)$表示对于子树$i$, 层次不超过$j$的最大值, 显然不能用这样的方程, 他的复杂度是$O(n^2)$. 不过我们可以从中考虑一些问题.

当$j=1$时, 我们把方程写过一下: $f(i)$表示子树$i$选一层的最大值, 转移方程为:

$$f(u) = max \{ v(u), \sum_{v \in son_u} f(v) \} $$

发现没有, 其实我们在算$k(j) = 1$的时候, 已经"算到了”$k = 2$的值(不管最大值是哪一个, 次大值加上$k=1$的值[就是这里做出来的最大值]就是$k=2$的值了), 只不过我们把他"放弃"了. 实际上我们可能还放弃了$k=3$甚至更多的值(这里也指"增量").

如果把这些值合理利用, 是不是就能够只跑一次了呢?

不妨这样想, 对每一个节点, 开一个大根堆, 维护的是$k$递增取值时的"增量", 即:

  1. 堆中的第一个元素是取一层得到的值
  2. 第二个元素是取两层在取一层上多加上的值
  3. 以此类推

如何维护这样一个堆呢?

和$dp$一样, 把这个堆当成$dp$的值即可, 它也是从儿子转移过来的. 让儿子的堆的对应位置相加, 然后再把当前节点的$v$丢进去就行了.

证明:

先证儿子对应位置相加的正确性: 由于各个儿子的选择是互相独立的, 而且儿子的堆中元素是排好了序的, 那么对应位置相加以后得到的新序列也是排好了序的, 所以对应位置直接相加即可.

再证丢进去一个$v$可行: 每做一个节点, 都新增一层, 所以把当前的$v$丢进堆里是必要的. 由于子树中, 各深度节点的选择是独立的, 所以根据贪心, 无论$v$在哪一个地方, 只要比子树的某些值更优, 即可选上$v$, $k$递增的时候再去选其他值($v$最小当然最后选$v$即可).

做完以后, 根的堆的前缀和就是答案了. 当然堆中元素很可能不满$n$个, 超过堆大小的$k$, 就已经可以全部选上了. 这些$k$的答案就是堆中所有元素的和(其实也就是所有节点的和).

合并堆的时候记得用启发式合并.

还有最后一个问题: 如何建树?

将线段按$l$从小到大, 长度从大到小(实际上可看成$r$, 因为$l$相等才比较$r$)排序, 可以发现, 这个顺序就是树的前序遍历. 开一个栈维护一条链: 如果栈顶线段不包含当前线段, 证明这两个线段不是父子关系, 那么栈顶出栈, 直到栈顶和当前线段是父子关系, 连边. 当前点入栈. 这样就可以$O(n)$建树了.

复杂度小于$O(nlog^2 n)$, 因为启发式合并的$O(logn)$跑不满. (官方题解证明了复杂度其实是$O(nlogn)$, 看不懂)

(官方题解太阴间, O(n^2)的dp一顿数学分析, 结果和我的做法一样…)

据说还有长链剖分的算法?? 有空学, 咕咕咕.

 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
const int maxn = 2.5e5+10;

struct Segment {
	int l, r, w;
	bool operator < (const Segment &S) const {
		return l == S.l ? r > S.r : l < S.l;
	}
} segments[maxn];

int n;

vector<int> son[maxn];
vector<int> stk;

void Build() {
	stk.push_back(0);
	for (int i = 1; i <= n; i++) {
		Segment &s = segments[i];
		int fa = stk.back();
		while (!(segments[fa].l <= s.l && s.r <= segments[fa].r)) {
			stk.pop_back();
			fa = stk.back();
		}
		son[fa].push_back(i);
		stk.push_back(i);
	}
#ifdef D
	printf("Tree:\n");
	for (int i = 0; i <= n; i++) {
		printf("%d:\n", i);
		for (auto v : son[i])
			printf("%d ", v);
		puts("");
	}
#endif
}

MaxHeap heap[maxn];
int idx = 0;

// 启发式合并
int Merge(int x, int y) {
	vector<LL> pool;
	if (heap[x].size() > heap[y].size())
		swap(x, y);
	while (!heap[x].empty()) {
		pool.push_back(heap[x].top() + heap[y].top());
		heap[x].pop(), heap[y].pop();
	}
	for (auto t : pool)
		heap[y].push(t);
	return y;
}

// 返回的是当前点的堆(的下标)
int dfs(int u) {
	if (!son[u].size()) {
		heap[++idx].push(segments[u].w);
		return idx;
	}
	int cur = dfs(son[u][0]);
	for (int i = 1; i < son[u].size(); i++) {
		int p = dfs(son[u][i]);
		cur = Merge(cur, p);
	}
	heap[cur].push(segments[u].w);
	return cur;
}

int main() {
	scanf("%d", &n);
	segments[0] = Segment{1, 1000000, 0};
	for (int i = 1; i <= n; i++) {
		int l, r, w;
		scanf("%d%d%d", &l, &r, &w);
		segments[i] = Segment{l, r, w};
	}
	sort(segments, segments + n + 1);
	Build();
	int p = dfs(0);
	LL ans = 0;
	for (int i = 1; i <= n; i++) {
		if (!heap[p].empty()) {
			ans += heap[p].top();
			heap[p].pop();
		}
		printf("%lld ", ans);
	}
	return 0;
}

给出两棵大小为$n$的树, 带边权, 节点标号为$1 ~ n$. 对于每一个节点$i$, 找到一个节点$j$, 使得在两棵树中, $i$到$j$的距离和最小. 求$j$.

$2 \le n \le 2.5 \cdot 10^5, 1 \le w \le 10^9$

距离先转为和$lca$有关的问题.

对两棵树点分治, 得到两棵重构的点分树. 这样一个点的$lca$最多只有$O(logn)$个.

先形式化一下, 设$T1, T2$分别为两棵树, $dist(T, L, i)$为树$T$中$i$的祖先$L$到$i$的距离.

对于每一个$i$, 枚举其两棵树上的祖先的组合$(L1, L2), L1 \in T1, L2 \in T2$, 然后我们求两棵以$L1, L2$为根的子树$T1(L1), T2(L2)$中, 共有的节点$j$, 求出到$L1$及$L2$距离和最小的$j, j \ne i$. 这样就求得了最小的$dist(T1, L1, j) + dist(T2, L2, j)$. 然后再对每一个$i$求一下$\min \{ dist(T1, L1, i) + dist(T2, L2, i), L1 \in T1, L2 \in T2 \}$

可以发现, 我们要求的$\min \{ dis(T1, L1, i) + dist(T2, L2, i) \}$和$\min \{ dis(T1, L1, j) + dist(T2, L2, j) \}$的形式是一模一样的. 所以, 我们不妨一起做: 对每个$i$枚举两个祖先的组合$(L1, L2)$, 先计算$dist(T1, L1, i) + dist(T2, L2, i)$. 再找到$dist(T1, L1, j) + dist(T2, L2, j)$最小值和次小值以及他们所对应的点. 如果取得最小值的点不是$i$, 那就加上最小值; 如果是$i$, 那就加上次小值.

$L$的大小至少为$2$(否则他是叶子, 叶子不可能是某个节点的祖先), 所以一定有最小值和次小值, 上述做法可行.

复杂度$O(nlog^2n)$

具体实现:

点分学习笔记

上面的点分是没有边权的, 只是把一棵树的结构重新构造了一下(还没做过题, 不知道重构会影响什么, 不会影响什么). 但是这里有边权, 我们重构的过程中, 甚至连边都重构了. 那么怎么办呢?

实际上, 我们不需要每一条边的权值, 所以不需要保存整棵树的结构, 需要的是$dist(T, L, i)$, 也就是重构的树中, 节点$i$到其祖先的距离. 找到一个重心以后, 从他开始dfs, 可以得到这棵树中每一个点到重心的距离. 而重心一定后代的祖先, 所以保存所有后代及其到重心的距离即可. 然后深搜儿子进行点分的时候, 某些后代(除了儿子以外的后代)又会新增祖先(子树的重心)及距离. 这样虽然没有保存重构树的结构 —— 根本不需要全部的结构 —— 但是保存了真正需要的东西: 祖先

仔细思考上述内容, 又可以得出结论: 重心一定是所有后代有的祖先(没有后代就不用管他). 那么我们在对第二棵树进行点分的过程中, 实际上已经在枚举$L2$了, 也就是重心$c$. 然后, 对于$c(L2)$的所有子代$v$, 遍历他在$T1$中的祖先$a$, 这样就枚举了$(L1(a), L2(c))$. 可以对每一个$a$开一个小根堆, 把$dis(T1, L1, i) + dist(T2, L2, i)$压入堆中. 做完这一步, 就可以开始找最小和次小了.

重新枚举$v$和$a$, 先找最小, 如果就是$v$再找次小.

由于只需要小根堆的前两个值, 所以不必用堆 —— 可以直接维护最小值和次小值, 这样就把堆的$O(logn)$减下来了.

注意对每一个$c$开始更新之前, 要重置"堆".

然后就做完啦啦啦!!!

  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
typedef pair<int, LL> PIL;
typedef pair<LL, int> PLI;

const int maxn = 2.5e5+10;

struct HeapTwo {
	PLI val[2];
	void Reset() {
		val[0] = val[1] = make_pair(INF, -1);
	}
	void Push(PLI x) {
		if (x < val[0])
			val[1] = val[0], val[0] = x;
		else if (x < val[1])
			val[1] = x;
	}
	LL Top(int u) {
		return val[u == val[0].second].first;
	}
} heap[maxn];

int n, size[maxn], vis[maxn];
vector<PIL> T[2][maxn], descendant, anscentant[maxn];

LL ans[maxn];

// 维护size用来点分, 同时记录点到根的距离.
void dfs(int k, int u, int f, LL dis) {
	size[u] = 1;
	descendant.emplace_back(u, dis);
	for (auto e : T[k][u]) {
		int v = e.first;
		LL w = e.second;
		if (v != f && !vis[v]) {
			dfs(k, v, u, dis + w);
			size[u] += size[v];
		}
	}
}

int Center(int k, int u) {
	// 每一次求重心的时候, 要重新求子代, 注意清空
	descendant.clear();
	dfs(k, u, 0, 0);
	int tot_size = descendant.size();
	for (auto des : descendant) {
		int is_center = 1;
		int x = des.first;
		for (auto e : T[k][x]) {
			int v = e.first;
			if (vis[v])
				continue;
			// size[x] > size[v] == v 是 x 的儿子
			if (size[x] > size[v] && (size[v] << 1) > tot_size) {
				is_center = 0;
				break;
			}
			// size[x] < size[v] == v 是 x 的父亲
			if (size[x] < size[v] && ((tot_size - size[x]) << 1) > tot_size) {
				is_center = 0;
				break;
			}
		}
		if (is_center) {
			// 找到重心, 需要以重心为根, 求一下子代到根(这个祖先)的距离
			descendant.clear();
			dfs(k, x, 0, 0);
			return x;
		}
	}
	return -1;
}

void Decomp0(int k, int u) {
	int c = Center(k, u);
	for (auto des : descendant)
		// c 为所有子代的一个祖先
		anscentant[des.first].emplace_back(c, des.second);
	// 删除c, 做剩下的森林
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp0(k, v);
	}
	// 深搜, 可回溯, 节省空间(虽然不是很必要)
	vis[c] = 0;
}

void Decomp1(int k, int u) {
	int c = Center(k, u);
	// 先初始化堆
	for (auto des : descendant) {
		int v = des.first;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			heap[a1].Reset();
		}
	}
	// 对所有(L1, L2), 把所有 dist(T1, c, v) + dist(T2, a, v) 压入堆
	// 得到每个(L1, L2)的最小值和次小值
	for (auto des : descendant) {
		int v = des.first;
		LL dis2 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis1 = ansc.second;
			heap[a1].Push(make_pair(dis1 + dis2, v));
		}
	}
	// 更新答案
	for (auto des : descendant) {
		int v = des.first;
		LL dis1 = des.second;
		for (auto ansc : anscentant[v]) {
			int a1 = ansc.first;
			LL dis2 = ansc.second;
			ans[v] = min(ans[v], dis1 + dis2 + heap[a1].Top(v));
		}
	}
	// 继续点分
	vis[c] = 1;
	for (auto e : T[k][c]) {
		int v = e.first;
		if (!vis[v])
			Decomp1(k, v);
	}
	vis[c] = 0;
}

int main() {
	scanf("%d", &n);
	for (int k = 0; k < 2; k++)
		for (int i = 1; i < n; i++) {
			int u, v;
			LL w;
			scanf("%d%d%lld", &u, &v, &w);
			T[k][u].emplace_back(v, w);
			T[k][v].emplace_back(u, w);
		}
	Decomp0(0, 1);
	for (int i = 1; i <= n; i++)
		ans[i] = INF;
	Decomp1(1, 1);
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	return 0;
}