2026 Public Problem 训练记录

0102

P8164 [JOI 2022 Final] 沙堡 2 / Sandcastle 2

https://www.luogu.com.cn/article/ztfmbbo6

考虑怎么刻画一个矩形是合法的：每个点连向比它小的最大值，最后形成一条链。因为每个点互不相同，所以有一个充要就是，给每个点一个 \(a_i-x\)（其中 \(x\) 是比它小的最大值，没有就是 \(0\)）的权值，如果当前点比周围四个点都要大则说明它是链头，就是 \(1e7-x\)。这样一个矩形如果是合法的，权值和就是 \(1e7\)。

这样就好做了，我们直接枚举上下边，然后从左到右扫描线右端点，求出有多少个合法的左端点即可。

0104

https://codeforces.com/contest/2180

D Insolvable Disks

好吧，这种套路我确实没见过。

考虑一个点 \(i\) 开始的连续相切段最远能够相切到 \(f_i\)，显然 \(f_i\) 是不减的。那么我们直接贪心取 \(x\to f_x,x+1\to f_{x+1},\cdots\) 就好了。

这是因为有这样：

--- ---

如果有一个下面的能够更优，必定是因为很长：

--- ---
 -------

但是这样的话，它就长过上面的第二段了，显然不合法。

所以直接贪心就是对的。

E No Effect XOR

阅读的是 https://www.luogu.com.cn/article/osdymemx。这里用到了异或一一对应的性质。我们希望 \([l,2^k)\) 异或上一个 \(x\) 后依旧是自己这个区间的值，那么相当于 \([0,l)\) 异或上 \(x\) 后依旧是自己区间内的值。

利用这个性质就很好做了。

F1 Control Car

没有用题解的做法，就是考虑我们将计数转概率，那么设计状态 \(f_{i,j,0/1,0/1}\) 表示从 \((1,1)\) 走到 \((i,j)\)，其中 \((i,j)\) 右上角是否向下，\((i,j)\) 左下角是否向右。直接 dp 就好了。只保存这两个是因为这两个可能关系到两次移动，而其他只关系一次移动。

F2 就是用矩阵乘法优化就好了。

G Balance

https://www.luogu.com.cn/article/8d19d6fz

我们需要注意到的是，原数列是一个回文串，所以可以正着算一遍，反着算一遍加起来得到答案的两倍，以此删除掉式子中的某些项。

这样我们就可以直接推式子做了。每次取出中位数其实也很有门道，看题解吧。主要就是发现一种数是模 \(4\) 周期的取出，我们直接从后往前扫就好了。

0105

P6168 [IOI 2016] railroad

这种题需要考虑使用欧拉回路建图。我们先建出每个速度的节点，然后考虑将 \(\le s\) 特化为 \(=s\)，然后加速不收钱，减速收钱。此时我们需要使得整张图所有边都被经过，所以就要补边。我们考虑：跨过某条边的加速边和减速边数量一样，根据这个补全图，然后图可能不连通，再用 mst 求出把图弄联通的最小代价即可。

https://www.luogu.com.cn/article/wu9wc3lb

P5294 [HNOI2019] 序列

首先需要学习保序回归。这里有一个很好看的保序回归的解释：

这是经典的「全序集上的保序回归问题（\(L_{2}\)）」，时间复杂度可以做到 \(O(n)\)。

Lemma 1. 如果 \(a_i>a_{i+1}\)，则最终取 \(b_i=b_{i+1}\) 一定不劣。

Proof. 考虑使用调整法，分为以下几种情况：

• \(b_{i} \ge a_{i+1}\)，做调整 \(b_{i+1}\gets b_{i}\) 一定不劣。
• \(b_{i+1} \le a_i\)，做调整 \(b_{i}\gets b_{i+1}\) 一定不劣。
• \(b_{i}<a_{i+1}<a_i<b_{i+1}\)，做调整 \(b_{i} \to a_{i},b_{i+1}\to a_{i}\) 一定不劣。

考虑一对 \(i,i+1\) 满足 \(a_{i}>a_{i+1}\)，不妨钦定 \(b_{i}=b_{i+1}\)，那么它们可以被合并为一个变量 \(x\)（保持序列其余位置不变），且代价函数为 \(f(x)=(a_{i}-x)^2+(a_{i+1}-x)^2\)。

https://www.luogu.com.cn/article/b8247llu

所以可以用单调栈维护上面的过程。

这道题我们就因为每次只会修改一个，所以先正着做一遍，反着做一遍，正反两个单调栈再加上中间这个。中间这个怎么合并呢？我们需要二分一下。注意到左右端点具有单调性，详见：https://www.luogu.com.cn/article/3cerr8vu

P6167 [IOI 2016] shortcut

二分答案，直接硬写出来式子，然后相当于不满足第一个就要满足第二个。判定是否存在一个建快捷方式的方案使得满足。把绝对值拆了之后是个二位偏序，但是会发现其中一维其实没有作用，如果不满足一定不优。所以可以直接做一维偏序，做到 \(O(n\log nv)\)。

https://www.luogu.com.cn/article/dc3hazci

0107

vp The 3rd Universal Cup. Stage 37: Wuhan 记录。

L. Subsequence

签到题。将序列排序后，枚举最小值和中位数，然后就可以算出最大值，check 一下对不对就好了。

非常可惜的是写急了，罚了两发。第二次甚至样例都没过/wul。

J. Dictionary

考虑直接在反串上建出 SAM，找到某个串对应的节点后，就是非常经典的将 fail 树上的子树内全部打上 tag，统计 tag 的点的数量。这个直接暴力 dfs，跑到一个已经被打了 tag 的点就跳出来就好了。

M. Flight Tracker

发现题目给我们的坐标非常奇怪，研究后发现是：将球心射到某个点上，形成的射线交球面的交点。我们发现我们可以根据两个这种坐标算出它们对应的两个点的距离，同时答案是凸的，于是直接三分就好了。

注意注意，acos 里面传入 1+1e-18 也会返回 nan，务必特判！

H. WildFire, This Is for You!

可以使用 Python。

考虑 checker 怎么写。枚举 \(|i|+|j|<k\)，然后令所有的 \(\gcd(x+i,y+j)\neq 1\)；并判断是否存在一个 \(|i|+|j|=k\) 使得 \(\gcd(x+i,y+j)=1\)。

我先忽略了后面那个条件。然后只要使得 \(x+i\) 和 \(y+j\) 存在一个共同的因子即可。我令这个因子是一个质数。那么就是 \(x\equiv-i \pmod {prime},y\equiv-j\pmod {prime}\)，暴力跑 crt 合并。发现竟然第二个条件莫名其妙成立了（大概因为 crt 合并出来的是最小解导致的），但交上去 wa 了。

发现是位数太长了。考虑优化，每次我们不会弄一个新的质数，而是把质数从头到尾枚举一遍，如果某个质数丢进去做 excrt 没有报错，就用这个，直接卡到了 1300 位，然后就可以通过了。

K. Las Vegas

题解为什么要上下界网络流/yiw？

最开始考虑的是 meet in middle，但是不太会做。考虑这个数据范围也有可能是网络流，所以建图。

二分图，左部点是游戏场，右部点是玩家。我们发现每个游戏场会有三种结果：我放最多的钱成为第一名，我放第一名的钱数让第二名赢，我摆烂不放让第一名赢。

这三种边有三种代价，所以每个游戏场向对应玩家连流量为 1，代价为对应代价的边。源点向每个游戏场连流量为 1，代价为 0 的边。

然后玩家要向汇点连边，我们枚举我能赢 k 场，其他人赢的场数都要小于等于 \(k\)，那么就每个人（除了我）向汇点连流量为 k，代价为 \(0\) 的边，而我则向汇点连流量为 k 代价为负无穷的边，这样我们就会尽可能把我的 k 个流量流完。

太神奇了，竟然就过了。确实这种负无穷边可以让某个边流完。

D. Odd and Even

再给我两个小时都做不出来。

感觉在大规模复述官方题解，建议先看了官方题解，然后再看这个，这里还写了具体怎么实现。

发现只和奇偶性有关，所以我们变成 01 串，再做一个前缀和（异或），就变成了新的 01 串（不过段数稍微有点多，但是这不重要，先不考虑）。

我们现在需要选择 \(r+1\) 个数，令相邻不同数对（或相同数对）尽可能多。其中第一个和最后一个必选。

考虑 p 最大怎么做，发现肯定是尽可能选不同的，设前缀和段数为 \(t\)，那么答案就是 \(t-1\)，但是可能 \(p\) 达不到，所以要和 \(p\) 取一个 min，并且这个答案和 \(t-1\) 的奇偶性要相同（因为最开始答案是 \((t-1)\bmod 2\)，每次加入一个新段，答案奇偶性一定不会变）。

考虑 q 最大怎么做，相当于令 \(p\) 最小。我们换个方向考虑：对于每个 \(p\)，算出其 \(r\) 最大能是多少。因为答案具有单调性，就可以二分然后得到对应的 \(p\)。

也就是我们需要求出每个 \(p\) 最大的 \(r\)。

考虑这么一件事情，如果同时有两个相邻的块不选，一定不优，可以选择其中一个使得 \(p\) 不变，\(r\) 变大。

就此，我们发现选择情况一定是若干个 「选-不选-选-...-选-不选-选」 合并起来的。每次我们可以选择这么一个极长连续段，将其选或不选的情况反转，使得 \(p\) 减少 \(2\)，\(r\) 减少一定值。

这很类似于反悔贪心，我们用小根堆每次弹出 \(r\) 最小的减小值即可，然后将新的 「选-不选-选-...-选-不选-选」 段加入堆中。注意第一段和最后一段是不能反转的（\(0\) 和 \(t-1\) 必选）。三个极长段 101 101 101，反转中间那个，会变成 101 010 101，相当于将相邻两个极长段合并起来。

直接用 set 合并是可以的，但是是 \(O(t)\) 的复杂度。发现主要是因为原本的 1 做了前缀和之后就会变成 1010101...，形成很多段。

但是注意到这些段长度一定为 1，也就是操作这些段只会让 \(r\) 减小一。我们可以假设这些段已经被处理了，只模拟最后 \(O(n)\) 次操作，那么如果输入的 \(r\) 比初始的 \(r'\) 还要大，答案就是初始的 \(r'\) 对应的 \(p'\) 算出的 \(2(r-r')+p'\)。

考虑怎么实现比较好看，我们将段分为三种：全 0 段，全 1 段，101...101 段，其中第三种段前后只能接全 0 段。全 0 段前后不能是全 0 段，否则可以合并，全 1 段同理。

全 0 段，全 1 段已经就是一段了，一整个加进去即可。而 101...101 段，经过前面全 \(p\gets p-1\) 的处理，会变成 「选-不选-选-...-选-不选-选」，也是一个段了，也可以直接加进去了。

然后就做完了，怎么感觉我讲的这么抽象呢？放个代码吧：https://qoj.ac/submission/1897592。

0108

P11994 [JOIST 2025] 外郎糕 / Uiro

我们注意到：

• 对于每种数，一定是前面全部选 +，后面全部选 -；
• 贪心的思路是：从小到大考虑每种数，初始全部为 +，从后往前看能改就改；
• 注意到这样每种数会形成一个分界线，这个分界线一定是递增的，所以我们可以离线询问，然后每次枚举一种数，二分其分界线，因为分界线递增，所以实际上我们只需要记录上一个分界线前面是哪些数，分界线后面的一定全部选择了 -，所以实际上我们知道每种数的实际取值。可以直接二分了。

P14392 [JOISC 2017] 都市 / City【通信题暂无法评测】

我们可以记录下“dfn” 和 “sz” 来判定。dfn 是一定要记录的，但是这样 sz 就记录不下来了。我们考虑加入一些虚拟节点来使得 sz 的种类不会太多，实际上只需要 512 种虚拟节点，增长率为 0.023 即可。

考虑一点朴素的想法：把 \(\text{dfn}\) 跟 \(\text{size}\) 都传进去，但大概需要 36 位。感性上考虑 \(\text{dfn}\) 更重要，我们尝试把 \(\text{size}\) 压到 9 位。

考虑做一个这样的事情：构造序列 \(f_0 \sim f_{511}\) 去拟合 \(\text{size}_x\)，每次找到最小的 \(i\) 使得 \(f_i \geq \text{size}_x\) 并加入 \(f_i - \text{size}_x\) 个虚拟节点，再在此基础上构造 \(\text{dfn}\) 序列。

考虑构造 \(f_i = \lfloor (1 + w)^i \rfloor\)，其中 \(w\) 是一个足够小的正实数。限制有 \((1 + w)^{511} \geq 2^{19}\) 以及 \(\sum (f_i - \text{size}_x) \leq 2^{19} - n\)。分析一下后一个限制：由于 \(f_i \leq (1 + w)\text{size}_x\) 故左侧相当于 \(w \sum \text{size}_x \leq 19wn\)，故至多有 \((1 + 19w)n\) 个点。

然后可以注意到 \(f_i\) 不需要严格地取 \(\lfloor (1 + w)^i \rfloor\)，可以这样： \[f_i = \max(1, w \times f_{i-1}) + f_{i-1}\] 这样就能避免前期增长过慢的问题。然后二分找到一个满足条件的 \(w\) 即可。一个满足条件的值是 \(w = 0.022\)。

0109

P8376 [APIO2022] 排列

发现我们可以实现乘法（一个放在左下，另一个放在右上，得到 \(xy\) 的贡献），或者加法（一个放在左上，另一个右下，得到 \(x+y-1\) 的贡献）。直接朴素二进制分解是可以拿到 \(91\) 分的。

考虑我们不一定每次只弄 \(2\)。我们可以是任意质数啊。我们用任意质数的方法 dp 跑出 \(\le 200000\) 的所有答案的最优解，然后每次对于一个 \(k\)，从 \(200000\) 枚举到 \(2\)，判断是否能整除，若能直接用乘法，否则就普通的减一除二暴力即可。

P8491 [IOI 2022] 囚徒挑战

我们可以记录当前看到的位数以及最高位是什么，这里我在比赛时陷入了思维固区，以为必须是在 \(A\) 看完，\(B\) 检查，再让 \(A\) 看。实际上可以 \(A\) 看完，\(B\) 检查完再把 \(B\) 也写上去，然后 \(A\) 检查完再写新的 \(A\) 上去……可以优化很多。

然后我们每次可以在下面全是 \(0\) 或 \(N-1\) 的时候直接返回，那么状态转移就是 \(f_0=2\)（注意有 \(0\) 节点哦），然后 \(f_i=\max f_{i-j}j+2\)。发现 \(f_20>5000\)，刚好够了，可以用了。

详见：https://www.luogu.com.cn/article/05q47uir

P5473 [NOI2019] I 君的探险【交互、随机化】

考虑图是一颗树，且每个点的父亲编号小于它的编号（测试点 10、11）怎么做。

容易想到二分，每次我们对于一个点 \(x\)，二分它的父亲的范围 \([l,r]\)，然后将 \([l,r]\) 都操作一遍，如果 \(x\) 变色了，就说明它的父亲就在 \([l,r]\) 内。

非常可惜的是，这题不允许区间操作。但是我们可以使用整体二分，每次做一个 \(f(l, r, p)\) 表示编号大于 \(r\) 而父亲范围在 \([l,r]\) 的点的集合是 \(p\)，每次转移则将 \([l,mid]\) 的点全部反转，然后将 \((mid,r]\) 中被反转的点加入集合 \(pl\)。将 \(p\) 中被反转的点加入 \(pl\)，没被反转的点加入 \(pr\)，递归执行 \(f(l,mid,pl)\) 和 \(f(mid+1,r,pr)\) 即可。

void solve(int l, int r, vector<int> p) {
	if (l == r) {
		for (int i : p) {
			report(l, i);
			num++;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	vector<int> pl, pr;
	for (int i = l; i <= mid; i++) {
		modify(i);
	}
	for (int i = mid + 1; i <= r; i++) {
		if (query(i)) pl.push_back(i);
	}
	for (int i : p) {
		if (query(i)) pl.push_back(i);
		else pr.push_back(i);
	}
	for (int i = l; i <= mid; i++) {
		modify(i);
	}
	solve(l, mid, pl);
	solve(mid + 1, r, pr);
}

考虑怎么进阶到正解。一种思路是直接套用到无限制的图上，但是我们会遇到一个小问题：如果一个点前面有偶数条边连向它，那么这个点不会产生任何的连边。

不妨考虑随机化，我们每次打乱我们考虑的排列，这样原本有偶数条边连向它的点可能就会变成只有奇数条边连向它。每次分治完后，将已经确定的边删除（这可以通过之后每次 modify 操作时先将已经确定的临点反转实现），再通过 check 操作将已经记录完的点踢出排列，循环上面的操作，就可以通过了。

注意需要特判第一个子任务，这个子任务可以写暴力。

#include "explore.h"
#include <bits/stdc++.h>
using namespace std;

namespace Sub1 {
bool s[510];
vector<int> g[510];
void explore(int N, int M) {
	for (int u = 0; u < N - 1; u++) {
		modify(u);
		s[u] ^= 1;
		for (int v : g[u]) {
			s[v] ^= 1;
		}
		for (int v = u + 1; v < N; v++) {
			if (query(v) ^ s[v]) {
				s[v] ^= 1;
				report(u, v);
				g[u].push_back(v);
				g[v].push_back(u);
			}
		}
	}
}
}

namespace Sub2 {
vector<int> g[200010];
int s[200010], num;

void solve(int l, int r, vector<int> p, const vector<int> &V) {
	if (l == r) {
		for (int i : p) {
			g[V[l]].push_back(i);
			g[i].push_back(V[l]);
			report(V[l], i);
			num++;
		}
		return ;
	}
	int mid = (l + r) >> 1;
	vector<int> pl, pr;
	for (int i = l; i <= mid; i++) {
		modify(V[i]);
		s[V[i]] ^= 1;
		for (int j : g[V[i]]) s[j] ^= 1;
	}
	for (int i = mid + 1; i <= r; i++) {
		if (query(V[i]) ^ s[V[i]]) pl.push_back(V[i]);
	}
	for (int i : p) {
		if (query(i) ^ s[i]) pl.push_back(i);
		else pr.push_back(i);
	}
	for (int i = l; i <= mid; i++) {
		modify(V[i]);
		s[V[i]] ^= 1;
		for (int j : g[V[i]]) s[j] ^= 1;
	}
	solve(l, mid, pl, V);
	solve(mid + 1, r, pr, V);
}
void explore(int N, int M) {
	mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
	vector<int> V;
	for (int i = 0; i < N; i++) V.push_back(i);
	while (1) {
		solve(0, (int)V.size() - 1, {}, V);
		if (num == M) break;
		vector<int> nw;
		for (int i : V) if (!check(i)) nw.push_back(i);
		V = nw;
		shuffle(V.begin(), V.end(), rnd);
	}
}
}

void explore(int N, int M) {
	if (N <= 500) Sub1::explore(N, M);
	else Sub2::explore(N, M);
}

这个算法为什么是正确的呢？我们发现对于一个度数为 \(k\) 的点，有 \(\frac{\lfloor k/2\rfloor}{k}\) 的概率前面有奇数条边连向它，当 \(k=3\) 时，上式取到最小值 \(\frac{1}{3}\)，也就是每次考虑的集合大小为 \(m\) 的时候，最坏情况下期望会使得集合大小减少 \(m/3\)（这里的最坏情况指的是给定的图的最坏情况，所以和期望并不矛盾），容易得到一个不严谨的式子：\(T(m)=T(m-m/3)+O(m\log m)\)，分析之后发现是 \(O(m\log m)\)。

0110

CF1540D Inverse Inversions【分块、max+卷积】

容易推出一个 \(O(\sum (n-x))\) 的做法，就是每次你发现我们考虑在 \(x\) 位置插入一个数之后，后面每个数，如果 \(a_i\le x\)，那么 \(x\gets x + 1\)，最后面答案就是 \(O(n-x)\)。

这个过程可以用分块优化，我们考虑一个块怎么快速求出以 \(x\) 进入后会变成什么。我们发现我们只需要维护以 \(x\) 进入后会加上 \(i\) 就行了。发现加上的值域只有 \(B\)，而输入的值域却有 \(n\)，果断换维。我们只维护 \(f_i\) 表示要加上 \(i\)，至少要 \(x\ge f_i\)。此时只有 \(B\) 个数要维护了。

考虑怎么计算一个段的 \(f\) 以及单点修改。考虑线段树。我们开个线段树算这个，那么怎么合并呢？我们可以发现，假设最终加了 \(k\)，其中 \(i\) 是在左边加的，\(j\) 是右边加的，\(i+j=k\)。那么 \(x\ge fl_i\)，然后变成 \(x+i\)，故 \(x+i\ge fr_j\)，也就是 \(x=\max(fl_i,fr_j-i)\)。所以 \(f_k=\min_{i+j=k} \max(fl_i,fr_j-i)\)。发现当 \(k\) 由 \((i,j)\) 转移过来时，\(k+1\) 一定由 \((i+1,j)\) 转移过来或者 \((i,j+1)\) 转移过来。所以可以 \(O(B)\) 合并。

建树就是 \(O(nB)\) 的，然后每次单点修改是 \(O(B)\) 的（真的学到了，可以用这种线段树来维护函数做到单点修改复杂度很小），查询直接二分根节点的值就好了。

平衡之后就是 \(O(n\sqrt{n\log n})\) 的。

P5284 [十二省联考 2019] 字符串问题【SAM、Easy】

https://www.cnblogs.com/bztMinamoto/p/10684233.html

最开始的思路就是将串反过来建 SAM，然后按照 parent 树连边跑拓扑求最长路即可。

但是但是，一个点可能是由多个串的，如果 \(a_i\) 和 \(b_j\) 在同一个节点上，且 \(|b_j| > |a_i|\)，此时它们就会连一个自环！但实际上 \(b_j\) 不是 \(a_i\) 的前缀！

所以我们对于每个节点，把所有串排个序，然后每个 \(B\) 串连向下一个长度的 \(B\) 串，以及这两个长度之间的所有 \(A\) 串，跑最长路即可。

P5285 [十二省联考 2019] 骗分过样例【数论】

要和我签订契约，成为出题人的 npy 吗？

有用的部分无非就是善用 factor 命令以及 miller rabin 了，注意求很大的数的莫比乌斯函数时，可以这么做：

• 先用 \(\le 10^6\) 的数把区间内的数能除就除掉。
• 此时区间内的数，要么是 \(1\)，要么是一个大质数（定义为 \(>10^6\) 的质数），要么是一个大质数的平方，要么是两个不同的大质数。
• 单独一个大质数可以用 miller rabin 判，一个大质数的平方可以 sqrt check 一下，否则就是两个不同的大质数了。

0111

D - Two Rooms【Ad-Hoc、爬山算法】

确实没想到啊。

假设当前所有人已经被分配到了房间 \(X\) 或房间 \(Y\)。总分定义为： \[ f = \sum_{i,j \in X} A_{i,j} + \sum_{i,j \in Y} A_{i,j} \] 假设人 \(i\) 现在处于 Bad State，即：

\[ \sum_{j \in \text{同房间}} A_{i,j} < \sum_{j \in \text{异房间}} A_{i,j} \]

如果我们将 \(i\) 从房间 \(X\) 移动到房间 \(Y\)，总分 \(f\) 会发生以下改变：

\[ \Delta f = 2 \times \left( \sum_{j \in Y} A_{i,j} - \sum_{j \in X, j \neq i} A_{i,j} \right) \]

显然这个值非负（因为发生调整时，人 \(i\) 总是处于 Bad State）。

同时，我们也知道，当某个人处于 Bad State 时，总有一种方法将总分增加。

所以，当总分最大时，所有人都处于 Good State。

这种东西太好了，所以其实直接退火也能过，这是因为调整代价一定是好的。

0112

P5781 [IOI 2019] 矩形区域【rect-trick】

前置阅读：Genius_Star 的题解。

定义连续段表示连续的 \([x,y]\)。

定义合法连续段表示一个连续段，并且「连续段最左端的右侧第一个比他大的数是连续段最右端」或「连续段最右端的左侧第一个比他大的数是连续段最左端」。

在我们枚举了右边界 \(r\) 和左边界 \(l\) 之后，我们需要求出有多少个 \(S_{l,r}\) 中的连续段 \([x,y]\) 使得 \(f_{x,y}\le l\)。上述题解中主要采用的方法是发现这样的连续段 \([x,y]\) 一定也是第 \(l\) 列的合法连续段（因为 \(f_{x,y}\le l\)），所以可以直接对第 \(l\) 列再跑一次单调栈求出所有合法连续段然后判断它是否真的 \(f_{x,y}\le l\)。

实际上，你可以直接先求出第 \(r\) 列的合法连续段，然后求出 \(S_{l,r}\) 的连续段，直接暴力找到所有被 \(S_{l,r}\) 的连续段包含的第 \(r\) 列的合法连续段，然后直接判定 \(f_{x,y}\le l\) 即可。这样复杂度之所以正确，是因为一个长度为 \(len\) 的连续段里，最多包含 \(O(len)\) 个合法连续段（合法连续段要么不交，要么包含），复杂度就是 \(O(\sum len)=O(nm)\) 的。

P3838 [IOI 2017] Toy Train【Ad-Hoc】

https://www.cnblogs.com/alfalfa-w/p/17309757.html

需要改变一下题目意思，然后你发现你可以排除一部分一定失败的点，如果没有一定失败的点，那么剩下的点全部都是一定成功的，否则可以递归下去继续做。

0113

P3700 [CQOI2017] 小 Q 的表格【数论、莫反、前缀和推式子 trick】

注意到题目给的东西可以直接进行变换：

\[ \frac{f(a,a+b)}{a+b}=\frac{f(a,b)}{b} \]

就是：

\[ \frac{f(a+b,a)}{a(a+b)}=\frac{f(a,b)}{ab} \]

这不是辗转相除法求 gcd 吗？我们继续看下去：

\[ \frac{f(a,b)}{ab}=\frac{f(\gcd(a,b),\gcd(a,b))}{\gcd(a,b)^2} \]

所以我们修改一个位置 \((a,b)\) 为 \(v\) 后所有 \(\gcd(x,y)=\gcd(a,b)\) 的位置都会被修改成 \(\frac{v}{ab}\cdot xy\)。

所以我们用树状数组维护一下 \(g(d)=f(d,d)\)。然后推式子，得到答案为：

\[ \sum_{d=1}^n \sum_{d|x}\sum_{d|y}\frac{g(d)xy}{d^2}[\gcd(x,y)=d] \]

简单推导：

\[ \sum_{d=1}^ng(d)\sum_{x=1}^{n/d}\sum_{y=1}^{n/d}xy[\gcd(x,y)=1] \]

莫反：

\[ \sum_{d=1}^ng(d)\sum_{x=1}^{n/d}\sum_{y=1}^{n/d}xy\sum_{p|x,p|y}\mu(p) \]

简单推导：

\[ \sum_{d=1}^ng(d)\sum_{p=1}^{n/d}\mu(p)p^2\sum_{x=1}^{n/d/p}\sum_{y=1}^{n/d/p}xy \]

设 \(S(m)\) 是 \(1+2+...+m\) 的前缀和函数，容易有：

\[ \sum_{d=1}^ng(d)\sum_{p=1}^{n/d}\mu(p)p^2S(n/d/p)^2 \]

关注后半部分，设 \(G(n)=\sum_{i=1}^{n}\mu(i)i^2S(n/i)^2\)。

使用一个不怎么众所周知的前缀和推式子的方法，就是考虑 \(G(n)-G(n-1)\) 的值，因为有 \((n/i)-(n/(i-1))=[i|n]\)，所以我们相减之后只用考虑这些项：

\[ G(n)-G(n-1)=\sum_{i|n}\mu(i)i^2(S(n/i)^2-S(n/i-1)^2) \]

考察 \(S(m)^2-S(m-1)^2\) 的值，实际上可以这么推：\((S(m)+S(m-1))(S(m)-S(m-1))=m^2\cdot m=m^3\)（\(m^2\) 可以用前缀和公式得到），所以有：

\[ G(n)-G(n-1)=\sum_{i|n}\mu(i)i^2(\frac{n}{i})^3 \]

即：

\[ G(n)-G(n-1)=n^2\sum_{i|n}\mu(i)\frac{n}{i} \]

后者可以使用狄利克雷卷积证明等于 \(\varphi(n)\)，也可以通过只看素数幂的情况来证明（证明了素数幂的情况下合法，因为卷积之后依旧是积性函数，所以得证），就是：

\[ \sum_{i|p^k}\mu(i)\frac{p^k}{i} \]

注意到只有 \(i=1\) 或 \(i=p\) 时 \(\mu\) 有值，所以就是：

\[ p^k-p^{k-1}=\varphi(p^k) \]

得证，所以 \(G(n)-G(n-1)=n^2\varphi(n)\)。

所以 \(G(n)=\sum_{i=1}^n i^2\varphi(i)\)，得到这个之后，直接跑数论分块即可。

P9730 [CEOI 2023] Grading Server【状态压缩、放缩法】

非常喜欢这种题目。

考虑转换一下题目，首先攻击系统的这个值没有必要和 \(0\) 取 \(\max\)，因为如果是负数肯定选择不攻击。先把自己的算力变成 \(c_H-f_G\cdot S\)，相当于每次可以将 \(c_G\) 减去 \(c_H\)，或者如果 \(f_G\) 还有的话，可以让 \(f_G\) 减 \(1\)，让 \(c_H\) 加上 \(S\)。对手同理。

整理一下上面的思路，就是有一个 \(A_0=c_H-f_G\cdot S,A_1=c_G-f_H\cdot S,f_0=f_G,f_1=f_H\)，这样每次的操作只和 \(f_0,A_0\) 或 \(f_1,A_1\) 有关了。每次可以选择下面两种操作：

• \(A_{k\oplus 1}\gets A_{k\oplus 1}-A_k\)；
• \(\text{if } f_k>0,f_k\gets f_k-1,A_k\gets A_k+S\)。

直接暴力就是设状态 \((A_0,f_0,A_1,f_1)\)，转移直接调换先后手位置，输就是 \(A_k+f_k\cdot S\le 0\)，然后直接去记忆化搜索即可。

手玩一些比较简单的结论：

1. 当 \(A_0\le 0\) 时，尽可能选择操作二（买血），原因是这时候攻击并不优。（买不了我就输了）
2. 当 \(A_0\ge S,A_1\le S\) 时，选择操作一（攻击），原因是这时候可以直接将对手打到 \(\le 0\)，而对手这时候就算选择买血，你也可以继续把它打到 \(\le 0\)。这时候，后手就会死亡。
3. 如果 \(A_1\ge S\)，选择攻击，因为选择买血的话，对手一攻击，我们的 \(f_0\) 不仅少了一次买血机会，而且 \(A_0\) 血量也变得更小了（我们只能让 \(A_0\) 加 \(S\)，但对手一攻击就前功尽弃了）。
4. 如果 \(A_0\ge 0,A_1\le 0\)，那么这时候我们需要尽可能选择买血，因为这样我们就会让自己变得 \(\ge S\)，对手就算买血也没有我们大（情况 3 直接把它打回原形），而且还攻击不了一点。如果能买血，那么后手就会死亡。

好像已经把很多情况覆盖完了？事实上加上这些剪枝，我们的 \(A_0\in[0,S],A_1\in[0,S]\)。

上面这些剪枝可以直接模拟（加一些小技巧），我们手模几个情况就好了：

先只考虑 \(A_0,A_1\) 是正数的情况，那么 \(A_0\ge S,A_1\le S\) 容易由情况二得到直接结束，当 \(A_0\le S,A_1\ge S\) 时，如果攻击完后 \(A_1'\ge S\)，那么直接结束（情况二），否则进入两个都是 \([0,S]\)。两个都 \(\ge S\) 时，最多只能坚持 \(\log V\) 轮。\(A_0\le 0,0\le A_1\le S\)，选择买血，如果还没能够回来，对方如果能买血就直接秒杀，否则我就会把血尽可能买到 \(\ge 0\)（每次相当于加上 \(S-A_1\)，因为对方一定会攻击）。如果是对方 \(\le 0\)，也是同理的，能买就买，买不了就攻击，交换之后变成上面的状态。两边都 \(\le 0\) 就是两边比谁先 \(\ge 0\)。

同时，我们注意到当 \(A_k+f_k\cdot S\le \max c(记作 V)\)，同时 \(A_k\ge 0\)，这时候可以得到 \(f_k\le V/S\)，所以我们发现状态数实际上是 \(O(S^2(\frac{V}{S})^2)=O(V^2)\)。

注意到我们的记忆化搜索存的是 \(0/1\)——先手赢或者输，非常不划算。考虑这么一件事情：当 \(f_0,A_1,f_1\) 相等时，\(A_0\) 越大先手越可能获胜（具有单调性），所以我们可以记录最小能使得先手胜的 \(A_0\)，然后就可以少掉一个状态。那么怎么转移呢？我们注意到我们可以二分这个值，然后直接判定一下 \(A_0\) 能不能赢，能赢就往下二分之类的云云。

现在这些能拿到 45 分。考虑做一些展开。

接下来我们需要利用性质，发现我们的值域都是 \([0,S]\)，这意味着，一旦我们回一次血，那么对手必须进攻（因为我们回血之后是 \(A\ge S\)，对手必须进攻）。

所以相当于我们每次是提升了 \(S-A_1\)，决策方不变。

设 \(\Delta_0=S-A_1,\Delta_1=S-A_0\)。

那么就是 \((A_0,f_0,A_1,f_1)\to (A_0+\Delta_0,f_0-1,A_1,f_1)\)。

注意到如果我们一直回血直到用完，之后攻击力如果比 \(S\) 还大，那么就可以获胜。

也就是 \(A_0+\Delta_0f_0\le S\)，否则先手获胜。

如果先手选择进攻，那么后手 \(A_1-A_0+\Delta_1f_1\le S\)，否则后手赢了。

这样又可以剪掉一些情况。

不要一直回血了，我们考虑夹杂一次进攻。

假设我们的战略目标为：先回血 \(x\) 次，然后攻击一次将决策权交给对手，然后对手回血完攻击之后我们把回血机会全部用完，最后直接放一次攻击消灭对手——假设我们目标就是这样。

对手如果知道了我们这个目标，肯定会尽可能在它的回合将回血机会用完（如果他就算把回血机会用完了，到了我的回合也能够把它打趴，那么我一定赢！）

推一推式子吧： \[ A_0'=A_0+x\Delta_0 \] 这里带撇表示新的。

那么显然有： \[ A_1'=A_1-A_0'+f_1(S-A_0') \] 同时，\(A_1-A_0+\Delta_1f_1\le S\)，否则我们只能回血。

因此： \[ \begin{aligned} A_1'&=A_1-A_0-x\Delta_0+f_1(S-A_0-x\Delta_0)\\ &=A_1-A_0-(f_1+1)x\Delta_0+f_1\Delta_1\\ &\le S-(f_1+1)x\Delta_0 \end{aligned} \] 此时 \(\Delta_0'\ge (f_1+1)\Delta_0x\)。

我们将 \(\Delta_0\) 增加了一个量级，但是被后手攻击了一次（不妨认为这个攻击攻击了 \(S\) 格血，即放成 \(S\)）

我们再防守 \(f_0-x\) 次，这时候 \(A_0''\) 就变成了 \(A_0''=A_0+x\Delta_0-S+(f_0-x)(f_1+1)\Delta_0x\)，缩成 \(-S+(f_0-x)(f_1+1)\Delta_0x\)，即 \((f_0-x)(f_1+1)\Delta_0x\ge 2S\) 时先手直接获胜。

二次函数最大值，不妨令 \(x=\frac{f_0}{2}\)，那么： \[ \frac{1}{4}(f_1+1)\Delta_0f_0^2\le 2S\\ (f_1+1)\Delta_0f_0^2\le 8S \] 也就是： \[ (f_1+1)(S-A_1)f_0^2\le 8S \] 因此，\((f_0,f_1,A_1)\) 的个数为 \(\sum\dfrac S{i^2}\ln S\) 的，利用 \(\sum\frac{1}{i^2}=\frac{\pi^2}{6}\) 可以证明这个式子是 \(\mathcal O(S\log S)\) 的。

注意需要特判 \(f_0=0\) 的情况，这种情况下方案数会爆（因为乘积是 \(0\)），处理方法很简单，直接进攻（甚至不需要计算，直接进入到 \((A_1-A_0,f_1,A_0,f_0)\) 即可）

0114

vp https://contest.ucup.ac/contest/1472。

L. 铁路环游【非常规思维、并查集】

一直想的是从代价函数的凸性上入手，结果正解和这个一点关系没有，果然还是被限制了思维。

考虑普通的 dp：设 \(f_{i,j}\) 表示考虑前 \(i\) 个轨道，连通了其中的 \(j\) 个，然后 \(i-1\) 连了 \(i\)。\(g_{i,j}\) 表示前面一样，但是 \(i-1\) 没有连到 \(i\)。

注意，这里将两个数组分开设，有利于优化 dp 的转移，不然可能会增加难度。

有转移：

\[ f_{i,j}=\max(f_{i',j'}+w(i',i))(i'-j'=i-j)\\ g_{i,j}=\max(g_{i-1,j},f_{i-1,j}) \]

注意这里 \(g\to f\) 的转移中 \(i-j\) 的值都是一样的，也就是说它们的转移是独立的。

所以我们维护 \(n\) 个数据结构，分别表示 \(d=i-j=0,1,\cdots,n-1\) 的最大的 \(d\) 值，每次我们扫描 \(i\)，然后将 \(r=i\) 的奖励的前缀 \(l\) 在数据结构中都加上 \(v\)，然后取出最大值，更新新的 \(g\)，把 \(g\) 插入数据结构末尾即可。

可以先扫描 \(d\) 再扫描 \(i\)，这样只需要同时维护一个数据结构，减小空间。

数据结构显然可以用线段树，但这很慢，因为每次都是前缀加正数，那么如果后一个数被前一个数偏序了，那么不需要记录后一个数，用并查集把他们合并起来，记录每个并查集到下一个并查集的差即可维护。

P5281 [ZJOI2019] Minimax搜索

参考：https://www.luogu.com.cn/article/kv8bsyq8。

我们先求出每个节点的权值，揪出贡献给根节点的那条转移链。要使得根节点的权值改变，我们需要修改某些值。

例如，转移链上的某个点 \(u\)，它的权值为 \(x\)，深度为奇数（取 \(\max\)），则它的儿子只需要有一个 \(>x\) 即可，方案就是它的每个儿子的方案的最小值。

而转移下去之后，例如儿子 \(v\)，它要大于 \(x\)，但是它这一层深度为偶数，即取 \(\min\)，则它的每个儿子都要 \(>x\)，方案就是它的每个儿子的方案的最大值。

直接跑线段树合并就可以维护了。

P3785 [SDOI2017] 文本校正【字符串、KMP、exKMP、马拉车、回文trick、AdHoc】

题目大意：给定两个长度为 \(n\) 的字符串 \(S,T\)，你需要判定 \(T\) 能否通过以下方式构造出来：

• 将 \(S\) 划分为三个非空连续段；
• 将这个三个非空连续段随意排列组合。

判断是否可以，如果能，给出方案。

\(n\le 10^6\)。

前置知识：在 KMP 算法中，模式串的每个前缀对应一个状态，其失配指针 \(\pi\)（也称 nxt 或 fail）定义了状态之间的后缀链接。由这些后缀链接构成的树结构称为 KMP 自动机的后缀链接树（fail 树），其中状态 \(i\) 的父节点为 \(\pi(i)\)。

设段编号为 \(1,2,3\)，将这三段的 \(3!=6\) 种关系分类讨论一下。

• \((1,2,3)\)

  与原串一样，直接判断是否相同即可。

• \((2,3,1)\)、\((3,1,2)\)

  是原串的循环同构，可以倍长后跑 KMP。注意题目要求三段都是非空的。

• \((1,3,2)\)、\((2,1,3)\)

  以 \(2,1,3\) 为例，\(S\) 和 \(T\) 具有相同的后缀，枚举这个后缀 \((p,n]\)，那么 \(T[1,p]\) 由 \(2\) 和 \(1\) 两个部分组成，求出所有是 \(T[1,p]\) 的后缀又是 \(S[1,p]\) 的前缀的字符串（将 \(T[1,p]\) 在 \(S\) 建出的自动机上跑了之后，得到的状态在后缀链接树上的所有祖先），它们就是可能成为 \(1\) 部分的字符串。设其中一个字符串是 \(S[1,k]\)，再判断 \(S[k+1,p]\) 与 \(T\) 的 lcp 是否超过 \(p-k\) 即可（使用 exkmp 计算出 \(z_{k+1}\) 即可判定）。取出 \(\max\{k+z_{k+1}\}\) 的祖先状态，这个可以在后缀链接树上预处理得到。

• \((3,2,1)\)

  将 \(T\) 前后翻转为 \(T'\)，就是判定 \(S\) 是否可以分成三段，使得每段和 \(T'\) 对应的段刚好前后顺序相反。考虑构造这么一个字符串：\(S_1,T'_1,S_2,T'_2,\cdots,S_n,T'_n\)，那么我们只需要判定是否能够将这个新的字符串划分为三段，使得每段都是回文串即可。存在一个引理：如果 \(s\) 是一个双回文串（对于一个字符串 \(s=ab\)，若 \(a,b\) 都是回文串，则称 \(s\) 为双回文串），则存在一种拆分方法 \(s=ab\)，使得 \(a\) 是 \(s\) 的最长前缀回文串，或者 \(b\) 是 \(s\) 的最长回文后缀。利用这个引理，算出以每个点为开头（结尾）的最长回文串长度即可判定。

引理的证明①如下。考虑引入一个新的引理：若 \(s=x_1x_2=y_1y_2=z_1z_2\)，且 \(|x_1|<|y_1|<|z_1|\)，\(x_2,y_1,y_2,z_1\) 是回文串，则 \(x_1\) 与 \(z_2\) 都是回文串。

设 \(z_1=y_1v\)。

\(v\) 是 \(y_2\) 的前缀，因为 \(y_2\) 是回文串，那么也是 \(y_2\) 的后缀。可以得到也是 \(x_2\) 的后缀，因为 \(x_2\) 是回文串，则 \(v\) 是 \(x_2\) 的前缀。

即 \(x_1v\) 是 \(z_1\) 的前缀。

因为 \(z_1\) 是回文串，所以：

\[ z_1=z_1^R=v^Ry_1^R \]

又因为 \(y_1\) 也是回文串，可以得到：

\[ y_1v=v^Ry_1 \]

所以容易有 \(z_1[i]=z_1[i+|v|]\)，即 \(z_1\) 存在一个长度为 \(|v|\) 的周期，换句话说，\(z_1\) 是 \((v^R)^{\infty}\) 的前缀，即 \(x_1\) 是 \((v^R)^\infty\) 的前缀。

同时我们也可以得到 \(x_1v\) 也存在一个长度为 \(|v|\) 的周期，所以 \(x_1\) 是 \(v^\infty\) 的后缀。

所以 \(x_1\) 是回文串。

如果字符串 \(s\) 存在至少三种划分方式，那么只需要最长前缀回文串即可判定，否则两种（一种）划分方式都会被我们考虑，得证。

①：字符串算法选讲 金策

0118

P6305 [eJOI 2018] 循环排序【欧拉回路】

考虑排列怎么做，先普通建出置换环，发现你可以用 \(x\) 的代价把某些置换环合并，现在问题变成了怎么把非排列变成排列。

我们需要定一个顺序，普通定顺序是哈密顿回路，考虑转成值域建图变成欧拉回路。

那么发现一个连通块就是一个欧拉回路，所以欧拉回路建图一定最优。

P9316 [EGOI 2021] Double Move / 二选一游戏【二选一trick】

类似Angle Beats 2.0的套路，我们发现建图之后的方案数由每个连通块的方案数相乘，一个连通块如果是树，方案就是点数（随意定根），如果是基环树，就是 2（环方向定义），否则是 0。

我们发现：

• 树+树=树
• 树+基环树=基环树
• 树+边=基环树

所以直接发现去记录基环树个数以及每个树的大小，然后爆搜即可。

0206

P9722 [EC Final 2022] Rectangle【线段树】

先令 \(x_2\gets x_2+1,y_2\gets y_2+1\)，转化为左闭右开区间。

分讨三横与两横一竖的情况，三横显然直接 dp 即可，考虑两横一竖。枚举竖线，相当于丢掉了一些已经满足条件的矩形，剩下的矩形就可以压成一个区间，我们需要计算有多少种 \((L,R)\) 满足 \(L<\min r_i,R\ge \max l_i\) 且不存在 \(L<l_i<r_i<R\)。考虑若固定了一个 \(L\)，则 \(R\) 的取值范围就是 \([\max l_i,\min_{L<l_i}r_i)\)，关键在于如何维护 \(\min_{L<l_i}r_i\)。考虑线段树分治加入这些修改，由于是前缀取 \(\min\) 所以可以转化成区间覆盖，直接做是 \(O(n\log^2 n)\)。

考虑怎么做单 \(\log\)。考虑换维扫描线，数据结构维护时间维的信息，由于是前缀改我们倒着扫，此时只需要支持前后缀取 \(\min\) 与查区间和，类似地可以直接转化成区间覆盖。当 \(\min_{L<l_i}r_i\le \max l_i\) 时还需要把该位置删掉，这个可以直接均摊维护。朴素线段树就可以完成上述事情，复杂度 \(O(n\log n)\)。

这里区间取 min 是因为，每次都是前后缀取 min，所以最后就是一个单峰函数，显然单峰函数取 min 的话，暴力做（维护区间 min max，如果 max 都比它小则退出，如果 min 比它大则区间覆盖，否则递归下去）只有 \(O(1)\) 个有用区间，所以依旧是对的

#6042. 「雅礼集训 2017 Day7」跳蚤王国的宰相【树的重心】

可以确定以下两条基本性质：

• 性质一：所有被断开的边，其中一个端点必然是原树的重心 \(p\)。即我们只断开与 \(p\) 直接相连的边。
• 性质二：所有断开后的连通分量，重新连接在目标节点 \(u\) 上是最优的。

性质二的成立是显而易见的。我们的目标是减小 \(u\) 在原树中“上方连通块”（即不包含 \(u\) 及其子树的部分）的大小，因为根据重心的性质其他子树的大小显然都是 \(\le \lfloor n/2\rfloor\)。将断开的子树重新连接到 \(u\) 节点上，可以直接从上方连通块中移除对应的节点数。由于原重心 \(p\) 的任何儿子子树大小 \(S\) 均满足 \(S \le \lfloor n/2 \rfloor\)，将这些子树挂载到 \(u\) 下作为其新的子树，不会导致 \(u\) 的任何下方子树大小超过 \(n/2\)。因此，这种重连方式在减小上方负担的同时，不会引入新的非法子树。

基于上述性质，我们只会断 \(p\) 周围的边。有两种删法：

• 只删 \(p\) 除了 \(u\) 子树外的边；
• 把 \(p\) 的一部分边删掉之后，再删 \(p\) 到 \(u\) 方向的那条距离 \(p\) 最近的边。

此时我们选择根据子树大小从大到小贪心断，直接二分即可。

为了证明只断开 \(p\) 的直接出边是最优的，我们需要对 \(p\) 的不同子树进行分类证明：

情况一：子树不包含 \(u\)

设 \(v\) 为 \(p\) 的一个儿子，且 \(u\) 不在 \(v\) 的子树中。若要从该方向消减 \(u\) 的上方重量，断开边 \((p, v)\) 优于断开 \(v\) 子树内部的任何边。因为断开 \((p, v)\) 能够一次性获得该子树最大的减重收益 \(size_v\)。任何更深层次的切割所获得的节点数必然小于 \(size_v\)，在断边代价相同的情况下，选择 \(p\) 的出边效率最高。而 \(size_v\le n/2\)，所以断开后直接接到 \(u\) 上是一定合法的。

情况二：子树包含 \(u\)

设 \(v\) 为 \(p\) 的一个儿子，且 \(u\) 位于 \(v\) 的子树中。此时，断开边 \((p, v)\) 同样是减重效率最高的方案。

证明：断开边 \((p, v)\) 后，包含 \(p\) 及其所有其他子树的结构被整体移走并重连至 \(u\)。此时 \(u\) 剩下的上方连通块变为了 \(v\) 子树内部除去 \(u\) 及其子树后的剩余部分，其大小为 \(size_v - size_u\)。

由于 \(p\) 是原重心，已知 \(size_v \le \lfloor n/2 \rfloor\)，因此 \(size_v - size_u\) 必然满足 \(\le \lfloor n/2 \rfloor\)。这意味着断开路径上最靠近 \(p\) 的这条出边，仅需一次操作即可使该方向的负担直接合法。而在 \(p \to u\) 路径中间进行的任何其他切割，移走的重量都更大，直接接到 \(u\) 上不一定能够合法。

综上，所有最优的切割方案均发生在原重心 \(p\) 的邻边上。通过对 \(p\) 的儿子子树大小进行排序和前缀和预处理，经过二分可以在 \(O(n \log n)\) 的时间复杂度内解决该问题。

#6043. 「雅礼集训 2017 Day7」蛐蛐国的修墙方案【搜索】

思维不能硬化啊，搜索也要面子的诶

建出置换环，发现大小为 \(2\) 的偶环可以直接判断，而大小 \(\ge 4\) 的偶环不会超过 \(25\) 个，且只有两种选择，可以 \(2^{25}\) 爆搜。

Dice Stats【概率、期望】

\(E[ans]\) 是容易用 dp 求的，然后方差怎么算呢？

有 \(P(A\land B)=P(A)*P(B|A)\)，这个 \(|\) 意思是条件，就是在 \(A\) 成立下 \(B\) 成立的概率是多少。

考虑怎么求 \(Var[ans]\) ，首先 \(Var[ans] = E[(ans - E[ans])^2]\) ，为了方便表达设 \(e = E[x]\) 。

先根据期望的线性化简一下式子：

\[ \begin{array}{l} V a r [ a n s ] = E \left[ (a n s - e) ^ {2} \right] (3) \\ = E \left[ a n s ^ {2} - 2 e a n s + e ^ {2} \right] (4) \\ = E [ a n s ^ {2} ] - 2 e E [ a n s ] + e ^ {2} (5) \\ = E [ a n s ^ {2} ] - e ^ {2} (6) \\ \end{array} \]

\(e^2\) 很好求，对于 \(E[ans^2]\) ，可以先把 \(ans = X_1 + X_2 \dots X_n\) 代入

\[ \begin{array}{l} E [ a n s ^ {2} ] = E \left[ \left(\sum_ {k = 1} ^ {n} X _ {k}\right) ^ {2} \right] (7) \\ = E \left[ \sum_ {k = 1} ^ {n} \sum_ {l = 1} ^ {n} X _ {k} X _ {l} \right] (8) \\ = \sum_ {k = 1} ^ {n} \sum_ {l = 1} ^ {n} E \left[ X _ {k} X _ {l} \right] (9) \\ \end{array} \]

但是由于 \(X_{k}\) 和 \(X_{l}\) 并不独立。所以不能拆开。所以只能硬算

\[ E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \wedge X _ {l} = j \right] * i * j \tag {10} \]

现在考虑 \(P[X_{k} = i\wedge X_{l} = j]\) 怎么算，先转化一下形式：

\[ P \left[ X _ {k} = i \wedge X _ {l} = j \right] = P \left[ X _ {k} = i \right] * P \left[ X _ {l} = j \mid X _ {k} = i \right] \tag {11} \]

但是 \(k\) 和 \(l\) 的取值太多，肯定不可以直接算。考虑继续化简 \(E[ans^2]\)

\[ E [ a n s ^ {2} ] = \sum_ {k = 1} ^ {n} E \left[ X _ {k} ^ {2} \right] + 2 \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] \tag {13} \]

\(E[X_k^2]\) 很好求，继续对后面的式子进行化简：

\[ \begin{array}{l} \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {k = 1} ^ {n} \sum_ {l = k + 1} ^ {n} \left(\sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \wedge X _ {l} = j \right] * i * j\right) (14) \\ = \sum_ {k = 1} ^ {n} \sum_ {l = k + 1} ^ {n} \sum_ {i = 1} ^ {6} \sum_ {j = 1} ^ {6} P \left[ X _ {k} = i \right] * P \left[ X _ {l} = j \mid X _ {k} = i \right] * i * j (15) \\ = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = k + 1} ^ {n} P \left[ X _ {l} = j \mid X _ {k} = i \right] (16) \\ \end{array} \]

对于显然 \(P[X_{l} = j|X_{k} = i]\) 可以这样转化形式：

\[ P \left[ X _ {l} = j \mid X _ {k} = i \right] = P \left[ X _ {l - 1} = j \mid X _ {k - 1} = i \right] \tag {17} \]

重复这个过程：

\[ P \left[ X _ {l} = j \mid X _ {k} = i \right] = P \left[ X _ {l - k + 1} = j \mid X _ {1} = i \right] \tag {18} \]

因此我们可以继续化简原来的式子：

\[ \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = k + 1} ^ {n} P \left[ X _ {l} = j \mid X _ {k} = i \right] (19) \\ = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] \sum_ {l = 1} ^ {n - k} P \left[ X _ {l + 1} = j \mid X _ {1} = i \right] (20) \\ \]

定义 \(F(i,j,k) = \sum_{l = 1}^{k - 1}P[X_{l + 1} = j|X_1 = i]\) ，由于 \(F\) 状态数只有 \(O(36n)\) 个，所以可以直接用下面的式子预处理：

\[ F (i, j, k) = F (i, j, k - 1) + P \left[ X _ {k} = j \mid X _ {1} = i \right] \tag {21} \]

最后就可以在 \(O(n)\) 的时间内通过下面的式子得出 \(\sum_{k = l}^{n}\sum_{l = k + 1}^{n}E[X_kX_l]\)

\[ \sum_ {k = l} ^ {n} \sum_ {l = k + 1} ^ {n} E \left[ X _ {k} X _ {l} \right] = \sum_ {i = 1} ^ {6} i \sum_ {j = 1} ^ {6} j \sum_ {k = 1} ^ {n} P \left[ X _ {k} = i \right] F (i, j, n - k + 1) \tag {22} \]

但是这样做由于转化成了 \(Var[ans] = E[ans^2] + e^2\) 分别计算，可能精度会有问题

考虑原式：

\[ \begin{align} Var &= E[(ans - e)^2] \tag{1} \\ &= E[ans^2] - e^2 \tag{2} \end{align} \]

由于\(E[ans^2] - e^2\)精度误差较大，所以考虑直接求\(E[(ans - e)^2]\)。由于\(e\)是已知的，所以可以对每个面的贡献都减去\(\frac{e}{n}\)，最后求和后就是\(ans - e\)，就是我们要求的式子。所以直接套用\(E[x^2]\)的做法即可。

0209

C - Divide into 4 Teams【生成函数】

首先列出生成函数，记录 \(A-B\) 和 \(C-D\)。那么一个元素就是 \(x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i}\)。就是要求 \([x^0y^0]\prod(x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i})\)。

此时我们进行因式分解：

\[ x^{P_i}+x^{-P_i}+y^{P_i}+y^{-P_i}=(x^{P_i}+y^{P_i})(1+x^{-P_i}y^{-P_i}) \]

设 \(S=\sum P_i\)。

前者是一个背包，当你选出了一个大小为 \(u\) 的元素分配给 \(x\)，就会产生 \(x^uy^{S-u}\) 的贡献。

后者也是一个背包，当你选出了一个大小为 \(t\) 的元素，就会产生 \(x^{-t}y^{-t}\) 的贡献。

显然有：

\[ u=t S-u=t \]

那么：

\[ u=t=S/2 \]

所以直接背包然后平方即可，注意需要减去空的情况。

F - Unpredictable Moves【网络流】

考虑怎么 check。

当出现以下情况，你是过不去的：

##

（直接相连）

#.
.#

（45度相连）

#
.
#

（跳一格相连）

根据经典结论：如果从右上角存在一个走这种 # 的方案可以走到左下角，那么就不能到达。

反过来我们就最小割，把每个墙拆点建一个 1 的边，然后直接连边即可。

G - Kyoen【数论】

实话实说，根本不会考哈哈哈。

先学习高斯整数。注意这里之所以 \(2\) 没有贡献是因为 \(2=(1+i)(1-i)\)，这两个质数实际上可以通过最后旋转 \(90\) 度得到，会算重。

然后这道题相当于你的 \((x\bmod C,y\bmod C)=(-A\bmod C,-B\bmod C)\)。同时因为 \(p_i\le 100\)，所以直接暴力找高斯整数分解是容易的（都是质数，可以枚举 \(x,y\)，使得 \(x^2+y^2=p\)）。但是注意到 \(e_i\) 很大，不过因为 \(C^2\) 很小，所以 \(x,y\) 存在周期，可以算出周期直接做。

F2. Again Trees... (hard version)【线性基、FWT】

先用线性基把 \(b\) 弄了，然后你发现设计 dp \(f_{u,i}\) 表示子树 \(u\) 内被砍掉的部分的异或在线性基内表示为 \(i\)。

转移是容易的，就是一个异或卷积，设 \(S\) 表示子树内异或和，然后你需要把 \(\sum_{b\in B}f_{u,S\oplus b}\) 加到 \(f_{u,S}\) 上。

每次 FWT、IFWT 复杂度多个 \(k\)，所以考虑全程不 IFWT。

这个其实也挺容易，分为两个部分，单点加、查询所有 \(S\oplus b\) 的和。

单点加是可以做到 \(O(2^k)\) 单次的，很容易。

后者你发现，假设 \(S=0\) 怎么做。

就是 \(P_i=[i\in B]\)，你要求：

\[ F_i\cdot P_i \]

就是一个点积。

不过我们有一个结论，设 \(\widehat{A}\) 表示 \(A\) 的 FWT 后的结果：

\[ \sum_{j=0}^{2^k-1} \widehat{A}_j \widehat{B}_j = 2^k \sum_{i=0}^{2^k-1} A_i B_i \]

所以我们可以先把 \(P_i\) FWT 后，然后两个做点积，再除以 \(2^k\) 即可。

这个证明也容易：

第一步：把定义代入左边根据定义，\(\widehat{A}_j = \sum_{i} A_i (-1)^{i \& j}\)（这里为了简洁，\(i \& j\) 代表 \(\text{popcount}(i \text{ AND } j)\) 的奇偶性）。

我们把左边的乘积展开：

\[ \sum_{j} \left( \sum_{i_1} A_{i_1} (-1)^{i_1 \& j} \right) \times \left( \sum_{i_2} B_{i_2} (-1)^{i_2 \& j} \right) \]

利用乘法分配律（就像 \((a+b)(c+d) = ac+ad+bc+bd\) 一样），把括号全部拆开：

\[ = \sum_{j} \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} (-1)^{i_1 \& j} (-1)^{i_2 \& j} \]

第二步：利用指数性质合并 \((-1)\)

注意到 \((-1)^x \cdot (-1)^y = (-1)^{x+y}\)。在位运算里，\(x\&j + y\&j\) 的奇偶性其实等于 \((x \oplus y) \& j\) 的奇偶性。所以公式变成：

\[ = \sum_{j} \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} (-1)^{(i_1 \oplus i_2) \& j} \]

现在我们调整求和的顺序（把对 \(j\) 的求和提到最里面）：

\[ = \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} \left[ \sum_{j=0}^{2^k-1} (-1)^{(i_1 \oplus i_2) \& j} \right] \]

第三步：分析那个“神奇的括号”这是整个推导最关键的地方。我们要看 \(\sum_{j=0}^{2^k-1} (-1)^{x \& j}\) 这个式子：

如果 \(x = 0\)（也就是说 \(i_1 = i_2\)）：那么 \((i_1 \oplus i_2) = 0\)。不管 \(j\) 是多少，\(0 \& j\) 永远是 \(0\)。\((-1)^0 = 1\)，所以这就是 \(2^k\) 个 \(1\) 相加。结果 = \(2^k\)。

如果 \(x \neq 0\)（也就是说 \(i_1 \neq i_2\)）：这是一个非常有意思的对称结构。如果你把所有的 \(j\) 遍历一遍，你会发现 \(x \& j\) 为偶数的情况和为奇数的情况正好各占一半。也就是有一半的 \(1\) 和一半的 \(-1\)。结果 = \(0\)。

第四步：见证奇迹的时刻

回到我们的公式：

\[ \sum_{i_1} \sum_{i_2} A_{i_1} B_{i_2} \times (\text{如果是 } i_1=i_2 \text{ 就贡献 } 2^k, \text{ 否则贡献 } 0) \]

因为只有当 \(i_1 = i_2\) 时这一项才不是 \(0\)，所以我们可以把 \(i_2\) 全部换成 \(i_1\)：

\[ = \sum_{i_1} A_{i_1} B_{i_1} \times 2^k \]

把系数 \(2^k\) 提出来，就得到了：

\[ = 2^k \sum_{i} A_i B_i \]

然后原本相当于你还要异或一个 \(S\)。相当于还要做一个卷积。这也容易。求出只有 \(S\) 的 FWT（\(O(2^k)\) 非常快），然后直接对位点积就求出来了。

0211

P6335 [COCI 2007/2008 #1] STAZA【仙人掌、圆方树 dp】

没什么好说的。

P4747 [CERC2017] Intrinsic Interval【数据结构、线段树】

不要只会 \(\max-\min=r-l\) 啊，换个思路，\((\sum_{i}[i\in S\land i+1\in S]) - (r-l)\) 也可以。前者能做但是大粪，后者小清新。

发现两个区间 \([l1,r1]\)，\([l2,r2]\) 如果相交且分别合法，那么它们的交也合法。所以我们每次扫描线右端点，用线段树区间 max 维护这个右端点对应的最大的左端点合法区间，然后扫到一个询问就加到堆里，每次取出一个左端点最大的询问，看看能不能被解决，如果能，其他解必定比它更劣，所以直接设答案，然后从堆里踢掉就行了。

0213

#10010. Kids And Sequence Game【单调性、局部博弈折叠】

将二进制看作是栈，每次选择一个栈顶弹出加到自己的价值那里，要求自己的价值与别人的价值差尽量大。

如果栈从顶到低单调递减，那么贪心就是对的。

如果一个栈上下是 \(x,y\) 且 \(x<y\)，那么如果先手选择 \(x\) 是最优的，那么后手选择 \(y\) 必然会使得先手产生负贡献，先手之所以这么做必然是想要选择 \(y\) 下面的那个 \(z\)，所以可以把三个数合并为 \(x-y+z\)，如果 \(z\) 不存在，那么 \(x\) 必然是最后取的。

用单调栈维护之后贪心即可。

0214

#10202. Exotic … Ancient City【最小生成树】

题目大意：给定一个 \(n\) 行 \(m+1\) 列的格点图。其中，第 \(i\) 列与第 \(i+1\) 列之间的连边方式、边权，和第 \(1\) 列与第 \(2\) 列之间完全一样。对于每一个 \(k \in [1, m]\)，求出只保留前 \(k\) 层（即前 \(k+1\) 列点）时，这张图的最小生成树权值和。

\(n,m\le 10^5\)，第 \(1\) 列与第 \(2\) 列之间有 \(\le 2\times 10^5\) 个点，边权最大为 \(30\)。

我们保留所有 \(w\le 1\) 的边，然后算出形成的连通块数量，假设是 \(x\)；然后保留所有 \(w\le 2\) 的边，算出形成的连通块数量 \(y\)，显然 \(w=2\) 的边加入了 \(x-y\) 条；然后保留所有 \(w\le 3\) 的边，算出形成的连通块数量 \(z\)，显然 \(w=3\) 的边加入了 \(y-z\) 条……以此类推，我们可以算出所有种边权的边的加入条数，从而算出答案。因为边权最大为 \(30\)，所以时间复杂度是正确的。而算法的正确性可以类比 Kruskal 的算法过程进行证明。

我们现在将问题弱化为了给定一些没有边权的边，求格点图的连通块数量。因为题目要求求出所有 \(k\) 的答案，不难想到去增量计算（求出每增加一列之后的答案）。

假如现在先算第一层（第一列和第二列）的答案，根据 Kruskal 算法的过程，我们最开始有一个边的集合 \(E\)（因为没有边权，所以无需排序）。这个集合中包括了第一层的所有边（更具体地，一条从第一列 \(u\) 连到第二列 \(v+n\) 的边在 \(E\) 中表示为 \((u,v+n)\)）。然后使用一个大小为 \(2n\) 的并查集维护前两列的点的连通性。其中 \(1\sim n\) 代表第一列的点，\(n+1\sim 2n\) 代表第二列的点。跑 Kruskal 就可以计算出连通块数量了（连通块数量为总点数减去在 Kruskal 算法过程中成功合并的边数）。

如果我们要算前两层的答案，实际上加入的边还是那些边，不同的是第二列的点已经初始具有一些连通性了。

我们将第一列与第二列的连通性情况“压扁”，意思就是说假如第二列有两个点 \(u+n,v+n\) 因为第一列的连边情况而在同一个连通块中，那么就当作存在一条 \(u\) 与 \(v\) 相连（注意这里不加 \(n\)）的虚边加入到 \(E\) 中。此时使用一个大小为 \(2n\) 的并查集维护二三列的点的连通性。其中 \(1\sim n\) 代表第二列的点，\(n+1\sim 2n\) 代表第三列的点，类比之前的算法就可以算出答案了：清空并查集，先继承第一层的答案，然后将 \(E\) 中的所有虚边都合并了（注意虚边的合并不会对答案产生贡献，只是为了初始化并查集），然后将 \(E\) 中的非虚边都合并了（如果两侧不联通，就会对答案产生 \(+1\) 的贡献）。

后面的每层做法都是类似的。之后我们将 \(1\sim n\) 代表的列称为左列，\(n+1\sim 2n\) 代表的列称为右列。

实际上我们可以更大胆，因为不存在边权，所以枚举 \(E\) 的顺序实际上是可以随意的。所以继承上一层的答案后，我们可以先将 \(E\) 中的非虚边都合并了（如果两侧不联通，就会对答案产生 \(+1\) 的贡献）。然后再枚举虚边合并，如果虚边两侧已经联通，那么说明形成了一个环，只需要在环上删除恰好一条边即可，那么答案 \(-1\)。

因为每次都会继承上一层的答案，我们可以维护答案的差分数组。

我们每次都要重新枚举 \(E\)，然后重新算并查集，显然并不优。再次应用 \(E\) 的顺序是可以随意的性质，我们按照一条边加入 \(E\) 的先后去枚举 \(E\)，相当于每次并查集不清空，先继承上一层答案的差分值，只考虑相较上次新加入 \(E\) 的那些虚边，在并查集上继续进行合并即可，如果加入的虚边两侧已经联通，那么差分值会 \(-1\)。

此时我们还需要判断合并两个点之后，是否会造成右列中两个连通块合并，从而形成新的虚边。这里就需要维护每个连通块中是否存在右列的点（\(>n\) 的点），如果是，随意取出一个就好（可以维护连通块中编号最大的点，每次判断这个点是否 \(>n\) 即可）。

因为最多会加 \(O(n)\) 条虚边（最多合并 \(O(n)\) 次），所以均摊之后复杂度就是 \(O(n\alpha(n)w)\)。

提交记录

#11219. Ferry【动态规划、丢弃无用状态、延迟贡献】

把船一直载满 \(3\) 个人是不劣的，多的空位我们用船夫补就好。故枚举所有可能的情况：

1. 一个船夫一直运输，把船上的两名游客送到对应目的地
2. 一个船夫一直运输，把船上的一名游客送到对应目的地，然后把一个船夫送到某个岛上
3. 一个船夫一直运输，然后把两个船夫送到某个岛上
4. 三名游客自己运输，然后在某个岛上接上船夫，让这个船夫把船运回 \(A\)

然后允许船夫在 \(B,C\) 岛不回来，因为真实情况下，如果有船夫在外面，我们在运他的时候干脆就不把他放下去就好了。

因为船夫具体在哪个岛不重要，我们只要知道「有几个船夫在 \(B,C\) 岛上即可」，所以我们利用延迟贡献的思想，就是每次把船夫运出去时，不思考它运到哪里了，要用的时候再确定。

因为贡献计算只考虑 \(t_i\) 最大的那个人，我们将 \(i\) 个人按照 \(t_i\) 从大到小排序，这么做有个好处，当我们要为这个人付费时，直接付费即可，后面的一些人就可以免费乘船。

意思是说，比如「一个船夫一直运输，把船上的两名游客送到对应目的地」这种情况，如果有一个 \(t_i\) 较大的人坐船到 \(B\) 岛，那么就可以免费带一个 \(t_i\) 较小的人到 \(B\) 岛。因为 \(t_i\) 从大到小排序，较小的那个人就不会产生贡献。

利用这种思想去设计 dp：\(F[i][x][y][z]\) 表示按 \(t_i\) 从大到小排序的前 \(i\) 个人已经计算过了贡献，有 \(x\) 个可以免费去 \(B\) 的机会和 \(y\) 个免费去 \(C\) 的机会，同时 \(B,C\) 岛还剩下 \(z\) 个船夫的最小花费时间。注意 \(z\) 可以为负数，表示提前预支船夫。

接下来假设当前人去的是 \(C\)，去 \(B\) 是类似的。转移如下：

• 送三个船夫出去（3 类船），\(F[i-1][x][y][z+2]\gets F[i-1][x][y][z]+3\)
• 载着一个游客，两个船夫出去一圈，放下一个船夫（2 类船），\(F[i][x][y][z+1]\gets F[i-1][x][y][z]+2w_i+1\)
• 自己开新的船，带一个船夫和一个到 \(C\) 的人（1 类船），\(F[i][x][y+1][z]\gets F[i-1][x][y][z]+2w_i+1\)
• 有一个到 \(B\) 的空位，支付改成 \(C\) 的价格，\(F[i][x-1][y][z]\gets F[i-1][x][y][z]+w_i-1\)
• 有一个到 \(B\) 的空位，支付改成 \(C\) 的价格的情况，也有可能是三个人一起出发去 \(B\)，这种情况下如果把一个去 \(B\) 的空位改成去 \(C\) 的空位，也可以把最后剩下的那个到 \(B\) 的空位免费改成到 \(C\) 的空位，\(F[i][x-2][y+1][z]\gets F[i-1][x][y][z]+w_i-1\)。当然这种情况也会把单独开了两只送 \(B\) 的船混淆，但是分析之后发现产生混淆的情况一定不优，所以不会算错
• 有一个到 \(C\) 的空位，免费使用了，\(F[i][x][y-1][z]\gets F[i-1][x][y][z]\)
• 三个游客一起出发，最后带回一个船夫，\(F[i][x][y+2][z-1]\gets F[i-1][x][y][z]+2w_i+1\)

此时复杂度非常大，不过我们发现，\(x,y\le 2\)。因为如果 \(x\ge 3\)，例如 \(x=3\)，一种情况是送了三只 1 类船到 \(B\)，那么贡献至少为 \(3w_i+6\)。而此时我们不如先送三个船夫出去（3 类船），然后再送两轮 4 类船，贡献是 \(3+2w_i+4=2w_i+7\)，前者一定不优于后者。其他情况也是类似分析即可。

而 \(z\in[-1,2]\)（实际上是 \([-1,1]\)，但我懒得分析了），下界证明，最多只会预支 \(1\) 个船夫，因为如果预支 \(2\) 个船夫，不如直接先送三个船夫出去从而满足条件，这样花费会更少。借此也可以证明最多只会多两个船夫（更严格地证明可以证出只会多一个船夫）。

所以复杂度正确。

0215

#15040. I Love CCPC【字符串、PAM、增量思想】

将操作离线，变成给定一个字符串，每次查询区间 \([l,r]\) 的答案，然后每次 \(l--\) 或 \(r++\)。

那么每次只需要查询以一个点为左端点、右端点的字符串个数即可，因为题目的 CCPC 串和回文串高度相关，所以直接建 PAM 乱做即可。

#6675. DS Team Selection 2【凸包、整体二分】

将全局加操作变成记录一个 \(k\) 表示 2 操作的次数，然后每次取 min 就是 \(v-ki\)，查询就是 \(\sum a+ki\)。

如果 \(a_i\) 初值为 \(+\infty\)，那么因为 \(k\) 不减，所以形成一个凸包，每次更新就是一个后缀，可以用线段树维护。

但是 \(a_i\) 有初值，我们求出一个 \(t_i\) 表示这个操作之后， \(a_i\) 就不是初值了。

可以使用整体二分，每次二分时跑一个凸包来实现。

0216

#15324. No more regrets【单侧递归线段树】

直接做，每次更新时需要跑两阶段的单侧递归线段树。

0217

#15303. Basic Counting Practice Problems【卷积优化 dp】

直接做 \(f_{u,j,k}\) 表示考虑 \(u\) 的子树，子树内编号为 \(1\sim siz_u\)，只允许走 \(\le j\)，能到 \(k\) 个点的答案。可以实现 \(O(n^4)\) 的 dp，但是内层转移是卷积，所以直接用 \(x=\{0,1,2,\cdots,n\}\) 作为点值跑卷积。难点在于求答案，我们需要求 \(A\cdot Q\)，但是我们只知道 \(\widehat{A}\) 的结果。我们类似拉插求系数的过程求出 \(M\) 使得 \(A=M\cdot \widehat{A}\)，那么就是 \(A\cdot Q=M\cdot \widehat{A}\cdot Q\)，预处理 \(M\cdot Q\) 即可快速求出答案做到 \(O(n^3)\)。

0218

Nonsense【生成函数】

设两个生成函数：

\[ A(z)=\sum_{i=0}\binom{i+a}{a}(xz)^i=\frac{1}{(1-xz)^{a+1}} \]

\[ B(z)=\sum_{i=0}\binom{i+b}{b}(yz)^i=\frac{1}{(1-yz)^{b+1}} \]

那么：

\[ f_{n,x,y}(a,b)=[z^{n-a-b}]A(z)\cdot B(z)=[z^{n-a-b}]\frac{1}{(1-xz)^{a+1}(1-yz)^{b+1}} \]

当 \(x=y\) 时，式子被简化为：

\[ [z^{n-a-b}]\frac{1}{(1-xz)^{a+b+2}}=\binom{(n-a-b)+(a+b+2-1)}{a+b+2-1}x^{n-a-b}=\binom{n+1}{a+b+1}x^{n-a-b} \]

只需要预处理 \(C_i=\binom{n+1}{i}\)，即可快速回答函数的值。这里的 \(i\le \max a+\max b+1\)，预处理它时间非常充足。

当 \(x\neq y\) 时，令 \(G_{a,b}(z)=\frac{1}{(1-xz)^{a+1}(1-yz)^{b+1}}\)，简写为 \(G(z)\)。同理，下文中的 \(f_{n,x,y}(a,b)\) 也被简写为 \(f(a,b)\)。

利用 \(\frac{1}{a}-\frac{1}{b}=\frac{b-a}{ab}\) 的思想，可以构造出如下式子：

\[ \frac{1}{(1-xz)^{a+1}(1-yz)^{b}}-\frac{1}{(1-xz)^{a}(1-yz)^{b+1}}=\frac{(1-yz)-(1-xz)}{(1-xz)^{a+1}(1-yz)^{b+1}}=\frac{(x-y)z}{(1-xz)^{a+1}(1-yz)^{b+1}} \]

即：

\[ G(a,b-1)-G(a-1,b)=(x-y)\cdot z\cdot G(a,b) \]

两边同时提取 \(z^{n-a-b+1}\) 的系数，得到：

\[ f(a,b)=\frac{f(a,b-1)-f(a-1,b)}{(x-y)} \]

可以递推求解。接下来需要考虑边界情况。

当 \(a=b=0\) 时，\(f(0,0)=\sum_{i=0}^n x^iy^{n-i}\)，容易用等比数列求和相关知识得到结果为 \(\frac{x^{n+1}-y^{n+1}}{x-y}\)。

当 \(a=0\) 或 \(b=0\) 时，以 \(b=0\) 为例。由于 \(G(a,-1)=\frac{1}{(1-xz)^{a+1}}\)，其系数为 \(\binom{n+1}{a}x^{n-a+1}\)。预处理 \(C_i\) 也可以快速计算 \(\binom{n+1}{a}\)。

所以也可以递推递推求得答案。

时间复杂度为 \(O(\sum (\max a_i)(\max b_i))\)。

Singularity【构造】

将 \(p_i\le n/2\) 看作 \(-1\)，否则看作 \(1\)。那么只需要把这个 \(-1,1\) 序列排好序，变为 \(-1,-1,-1,\cdots,1,1,1\)，最后再进行一次 \(FakeSort(1,n)\) 即可。

考虑怎么对一个区间进行排序，我们先考虑 \(n\ge 8\) 的情况。此时只有 \(-1,1,-1,1,\cdots,-1,1\) 或 \(1,-1,1,-1,\cdots,1,-1\) 是无解的，原因显然，任何偶数长度区间中 \(1\) 和 \(-1\) 的个数相等，进行 \(FakeSort\) 后序列不变。

剩下情况都有解。

定义 \(Sort(l,r)\) 函数，要求区间 \([l,r]\) 内 \(-1\) 和 \(1\) 的个数不同。以 \(-1\) 比 \(1\) 多为例。

此时假设 \(-1\) 和 \(1\) 的个数差为 \(2k\)，那么先进行 \(FakeSort(1,n)\)，然后再进行一次 \(FakeSort(l,r)\) 后，一般可以将后 \(k\) 个 \(-1\) 与前 \(k\) 个 \(1\) 交换位置。

此时后缀会有一段长度的 \(1\)。将后缀的偶数长度的 \(1\) 删去，继续重复上面的流程，直到成功排序。

因为每次一般可以删除后缀 \(\ge k\) 长度的 \(1\)，故每次 \(k\) 会翻倍，所以只会调用 \(2 \log n\) 次 \(FakeSort\)。

而因为 \(Sort(l,r)\) 要求区间内 \(-1\) 和 \(1\) 的个数不同，所以不能直接排序。

假如我们能够找到一个前缀 \([1,i]\)，满足前缀和的绝对值为 \(2\)，且至少有两个 \(-1\)，那么可以 \(Sort(1,i)\)，再 \(Sort(3,n)\)，使得序列成功排序。

而如果我们能够找到前缀和的绝对值为 \(2\)，但是没有两个 \(-1\)，要么只有两个 \(1\)，要么有一个 \(-1\) 三个 \(1\)。

如果只有两个 \(1\)，因为 \(n\ge 8\)，\(1\) 的个数至少为 \(4\)，所以后面也至少有两个 \(1\)。此时先 \(Sort(i+1,n)\)，再 \(Sort(1,n-2)\) 即可排序。

如果有一个 \(-1\) 三个 \(1\)，如果 \(n\ge 10\)，那么后面也至少有两个 \(1\)，先 \(Sort(i+1,n)\) 再 \(Sort(1,n-2)\) 也可以。但如果 \(n=8\)，那么 \(Sort(1,4)\) 再 \(Sort(5,8)\) 后序列就变成了 \(-1,1,1,1,-1,-1,-1,1\)，针对这个序列给出一个构造即可。

如果我们找不到前缀和的绝对值为 \(2\)，我们两个两个位置看，要么是 \(-1,1\)，要么是 \(1,-1\)，而每个奇数位置前缀和都是 \(1\) 或 \(-1\)。只有其中一种正负性的前面证明了无解，其余情况，我们找到最远的一对前缀和分别为 \(-1\) 和 \(1\) 的位置 \(x,y\)（\(x < y\)），可以证明在 \(n\ge 8\) 的情况下这两个位置差 \(y-x\ge 4\)，那么中间至少有一个 \(-1\)，一个 \(1\)。

\(Sort(x+1,y)\) 后，如果 \(x\) 位置前缀和为 \(-1\)，而 \(x+1\) 位置的值肯定是 \(-1\)，所以 \(x+1\) 位置前缀和绝对值为 \(2\)。如果 \(y\) 位置前缀和为 \(-1\)，因为 \(y\) 位置的值排序后肯定是 \(1\)，所以 \(y-1\) 位置的前缀和绝对值为 \(2\)。

也就是说，进行上面的操作后，一定可以找到前缀和绝对值为 \(2\) 的位置。

对于 \(n\le 6\)，可以直接乱搞。

操作次数为 \(4\log n+O(1)\)。

0223

#8207. Anton's ABCD【动态规划、等价类】

考虑给每个字符串等价类找一个代表元。不难发现对于一个字符串：

ABACDABCD

我们从左往右维护一个 stack，如果 stack 头顶 4 个是 ABCD 的循环位移，那么就 pop 掉，m++，最后就是 m*'ABCD' + stk中剩下的字符串：

ABCDABACD

所以我们先对输入串做这个变换，然后最后面相当于我们剩下 ABACD 这个垃圾串，我们要往垃圾串中插入 m 个 ABCD 的循环位移。

但是注意到插入串之后可能会出现重复计数的情况。我们定义：每次插入的串必须满足从后往前扫的时候，第一个 ABCD 的循环位移就是这个串。

那么对于一个原本的串 _ A _ B _ A _ C _ D _，除了最后一个空位，前面的都只有 \(3\) 种 ABCD 的插法，最后一个有 \(4\) 种。因为 A 前面插 ABCD 和在 A 后面插 BCDA 效果一样，而前面那个不满足定义。

而且，在某个位置插了之后，前面都不能插了。

转移就是 \(f_{i,j}\) 表示插了 \(i\) 个串，目前能插的位置有多少个，然后枚举插哪里进行转移，前缀和优化可以做到 \(O(n^2)\)。

#7943. LIS on Grid【Dilworth 定理、构造】

Dilworth 定理：最大反链的元素数量等于最小链划分中链的数量。

那么给图上连边，右下就是反链，右上就是链。就是要链划分。

答案是满足下式的最大 \(k\) ：

\[ \sum_{i=1}^{m} \max(0, a_i-k) \leq k\cdot (n-k) \]

若答案为 $ k $ ，则存在将所有黑格划分为 \(k\) 个不相交的链的方法。

先证明必要性。

如果 \(a_i\le k\)，我们发现我们可以直接将 \(k\) 条链直接向右延伸。而如果 \(a_i>k\)，就说明有一些链要占用两个以上的格子。而链只能向右上走，上升就无法下降，意思是说，我们第 \(i\) 列所有链的「上升次数之和」是 \(a_i-k\)。

而最优情况下，是从 \((n-k+i,1)\) 开始走到 \((i, m)\)，上升 \(n-k\) 次，总共 \(k(n-k)\)。不能大于这个了。而如下构造可以达到这个上界以证明充分性：

首先将 $ a_i<k $ 的都改成 $ k $ ，构造方案之后再在第 $ i $ 列删掉 $ k-a_i $ 格。接下来在网格上构造 $ k $ 个单调不增的序列，第 $ i $ 个序列从 $ (n-k+i,1) $ 开始，每列都至少有一格。设 $ b_i=a_i-k $ 。

每次构造一条链的单调不增序列，第 $ i $ 个链，按列递增的顺序假设当前在第 $ c $ 列： 1. 若 $ b_c>0 $ 且上方格子是白色，则向下走一步并将 $ b_c $ 减少 $ 1 $ ，将这个格子加入当前链中。 2. 向右走一步并将这个格子加入链中。

#7939. High Towers【构造、Hard】

https://qoj.ac/problem/7939/discussion/1108

我能说什么。

0224

1. 河神【杨表】

最优答案是 杨表 黑白染色后的较多值。

杨表 元素数量不是很多，预处理出每个杨表，然后对于每个杨表算 \(n/p\) 里出现了多少次。

杨表压缩重复值后只有 \(500\) 多个

用 unsigned long long 减少除法常数，必要时可以直接打表以编译期优化。

2. 传说【DP、计数】

前缀 mex 可以确定后缀 min，那么就可以求出每个数出现的区间，这些区间要么包含要么不交，形成树结构。直接跑一遍计算即可。

3. 生日礼物【💩、点减边、可持久化历史和线段树】

我竟然写完了？？？

思考怎么计算 \(w(l,r)\)。建出二维矩阵 \(u(l,r)\) 表示这个区间是否合法。我们发现利用点减边，那么就是矩阵 \(+2\) 或 \(-1\)。

注意还有链的限制，怎么办呢？可以发现，如果对于一个点度数 \(\ge 3\)，因为编号是连续的，所以只要有三个连续编号都出现了，那么就把对应矩阵加 \(1\)。

因为点减边至少是 \(2\)，而一旦加 \(1\) 就至少是 \(3\)。所以一个 \([l,r]\) 产生贡献当且仅当它是 \(2\)。\(w(l,r)\) 相当于区间查历史 \(2\) 的出现次数和。

使用可持久化历史和线段树即可。注意这里懒标记下传要开新节点，而查询时要标记永久化。

接下来考虑答案。\(k=1\) 直接枚举分界点计算 \(w\) 完事。而我们设计 \(f(n,k)\) 表示长度为 \(n\)，\(0\) 的那个地方必须要切（大概这个意思，就是第一段从 \(1\) 开始），的答案。

那么答案就是 \(f(2n,2k+1)-f(n,k+1)\)，不知道为啥。

\(f\) 直接 wqs 二分加上二分队列决策单调性即可。

0226

重塑记忆【简单】

6

众里寻他 / #7677. Easy Diameter Problem【dp、延迟贡献、延迟钦定、树】

因为是每次删一个直径端点，当直径长度是偶数时，直径中心是一个点，必然是直径中心点除了一棵子树的其它子树所有最远点被删空，有一棵子树则有所保留。

当直径长度是奇数时，直径中心是一条边，必然是直径中心边的一端的所有最远点被删空，另一端则有所保留。

我们把 \(n-1\) 条边拆成 \(2n-2\) 条有向边，记状态 \(f_{i,j,k}\) 表示直径长度为 \(i\)，直径中心为 \(j\)，这里的意思是说，当直径长度为偶数时，\(j\) 代表的边是 \((u\to v)\)，直径中心就是 \(v\)，而除了 \(j\) 这条边指向的子树，距离 \(v\) 的距离为 \(i/2\) 的点都还在，而 \(j\) 指向的子树则是距离 \(<i/2\) 的都还在，而距离为 \(i/2\) 的已经被删掉了 \(k\) 个（我们不记录是哪 \(k\) 个，我们在最后面抛弃时再指定他们，利用了延迟钦定的思想）。\(i\) 时奇数时，直径中心是一条边，就是 \(j\) 代表的这条无向边。而 \(u\to v\) 指向的那边 \(<floor(i/2)\) 的点都还在，而刚好为 \(floor(i/2)\) 的删掉了 \(k\) 个，另一边则 \(\le floor(i/2)\) 的点都还在。

这个可以转移，比如说奇数时，具体就是我们存下两边距离它刚好为 \(i/2\) 的点的数量 \(a,b\)，看是哪边先删光，就是 \(g_{a,b}\) 表示两边分别删了多少多少的方案，\(g_{a,0}=f_{i,j,a}\)，然后直接 \(g_{a,b}\gets g_{a,b-1}+g_{a-1,b}\)。注意得到答案时为了刚好时删光一边，就需要用 \(g_{a-1,k}a!\) 或者 \(g_{k,b-1}b!\) 去贡献，这里乘上阶乘就是给这些点标号。

偶数时还需要枚举是哪一个子树没被删光，假设这个子树大小为 \(c\)，那么就是 \(g_{a-c,b}\)（当然一样的，为了保证刚好删光，那么就是 \(g_{a-c-1,b}\) 或 \(g_{a-c,b-1}\) 乘上一个组合数和两个阶乘）

复杂度是 \(O(n^2)\) 的，一个是因为状态数就是平方的，另一个是转移时可以看作选择两个点去贡献，那么也是平方的（其实是我不会）。

3. 金字塔 / P8922 『MdOI R5』Squares【数据结构、线段树二分、调整法】

先判定 \(-1\)，因为 \(-1\) 一定是以查询的点为 左下角、右下角、左上角……之类的无穷大矩形，所以看看查询点的左上右上等等四个方向是不是至少有一个是没有点的，如果是就是 \(-1\)。

然后我们发现可能成为答案的矩形一定满足贴着至少三个点，用线段树二分对于每个点找到其对应矩形，然后现在我们有 \(O(n)\) 个矩形需要求答案。

朴素想法是树套树，两个 log 常数又大。现在我们抽出外层线段树的一条线，此时相当于有若干个区间，每个区间有一个权重，权重等于区间长度。利用这个性质，我们直接单调队列维护，也就是线段树套单调队列，就可以做到单 log。

0227

1. 简单树上问题【随机化、点分治】

直接给每个点随机赋权 \(1\sim 5\) 跑暴力即可。

但其实存在确定性做法，先点分治，考虑固定根怎么做。

就是你每次 dp 可以考虑先把 dp 数组传下去，然后再传上来，就是每次 dp 加入一个点。那么你发现，我们是一个类似子集卷积的转移，就是每次加入的那个点的颜色不能出现过（如果出现过，那第一次出现这个点时就不应该加进去（可以加进点数，但不能更新出现点的颜色集合））

维护 \(f_{i,j}\) 表示当前处理到 \(i\)，已经出现了 \(j\) 种颜色对应的最优解以及最优解的那 \(j\) 种颜色的集合。如果只这么干，那么加入当前颜色时，如果这个颜色在最优解的 \(j\) 种颜色中出现过就不行了。

所以我们对于一个 \(j\)，需要维护 \(j+1\) 个方案，表示无限制、不能有无限制方案中第一种颜色的方案、不能有无限制方案中第二种颜色的方案、等等等等……

转移应该是比较容易的。状态数的常数就是 \(2+3+4+5=14\)。

2. 时间旅行 / P6270 [湖北省队互测 2014] 十万人的地铁 【上下界证明、构造、置换环】

首先考虑答案的下界。设 \(s',t'\) 分别为 \(s,t\) 排序后的数组，根据经典结论 \(\sum\limits_{i=1}^n|s'_i-t'_i|\) 是答案的一个下界。

接下来通过构造来证明可以取到这个下界。

假设 \(s'_i\) 在 \(s\) 中是第 \(x\) 项，\(t'_i\) 在 \(t\) 中是第 \(y\) 项，那么第 \(x\) 个人要把物品给第 \(y\) 个人。建出 \(x\to y\) 的边，将这种关系记作 \(p_x=y\)，可以发现 \(p\) 是一个排列。如果能够对 \(p\) 中的一个置换环给出构造，那么就能给出全局的构造。接下来对 \(p\) 中的一个置换环进行分析。

若置换环大小为 \(1\)，直接移动这个人即可，接下来认为置换环大小 \(\ge 2\)。

令置换环中 \(s\) 最大的点为 \(x\)，\(p_x=y\)，也就是 \(x\) 把东西给 \(y\)。可以发现 \(s_y\le s_x\)（因为 \(s_x\) 是最大值），根据定义也可以得到 \(t_x\le t_y\)（因为 \(t_y\) 是最大值）。那么，它们的相对位置关系有下面几种：

其中省略了 \(s_x=s_y\) 或 \(t_x=t_y\) 的特殊情况。根据下面的分析，这种情况事实上不需要特殊考虑。（但是取出 \(x\) 时需要取出 \(s\) 最小其次 \(t\) 最大的那个）

对于情况 \(3,4,5\)，有 \(t_x\le s_y\)。此时，可以执行操作 \(0\ x\ s_y,1\ x\ y,0\ y\ t_y\)，这样 \(y\) 就得到了 \(x\) 的物品。可以认为新产生了一个 \(s_y\to t_x\) 的人，手拿 \(y\) 的物品。由于 \(x,y\) 在置换环上相邻，置换环上的变化是直接去掉了一个点。这样就递归到了子问题。

对于情况 \(1,2,6\)，有 \(s_y\le t_x\)。此时，还是认为新产生了一个 \(s_y\to t_x\) 的人，手拿 \(y\) 的物品。那么做完其他所有操作后，只剩下 \(x,y\) 两个人，且 \(y\) 在 \(t_x\) 处。执行操作 \(0\ x\ t_x,1\ x\ y,0\ y\ t_y\) 即可。

开两个栈，一个维护正序操作，一个维护倒序操作。总复杂度 \(O(n\log n)\)，\(s\) 在 \(3n\) 级别。

3. 序列变换 2 / #10100. Exchanging Kubic 3 【前缀和、上下界证明、构造、数据结构优化 dp】

把 \(a_i\) 加到 \(a_{i+1}\) 或者 \(a_{i-1}\) 上，经典的技巧是用前缀和数组 \(b\) 来表示，每次选择一个 \(b_{x}<b_{x+1}\)，然后把 \(b_x\) 变成 \(b_{x+1}\) 或者把 \(b_{x+1}\) 变成 \(b_x\)，注意不能修改 \(b_0\) 和 \(b_n\)。

要求把 \(b\) 改成不降序列。

设最终的 \(b\) 为 \(c_0 \dots c_n\)。

可以发现，一定能将 \(c\) 划分为若干个值相等的区间，并且对于每一个划分出的区间 \([l,r]\)，一定存在 \(x \in [l,r]\)，满足 \(b_l \le b_x \le b_r\)，且 \(c_{l \dots r}\) 全部都是从 \(b_x\) 扩展而来的。

对于这样的一组 \(l,r,x\)，可以知道其代价为

\[ r - l + \sum_{i=l}^x [b_i > b_x] + \sum_{i=x}^r [b_i < b_x]. \]

下界是容易证明的，至少要这么多。而上界先拿左边来看，就是可以把 \(\le b_x\) 看作 \(0\)，\(>b_x\) 看作 \(1\)。形成一个 \(01\) 序列，而最左边一定是 \(0\)，那么你可以每次把最前面的 \(1\)（这个 1 前面一定是 0）操作变成 \(0\)，所以操作这么多遍就变成全 \(0\) 了，最后再一起从头到尾做一遍就好了。

考虑钦定一组

\[ 0 = x_0 \le x_1 \le \dots \le x_m = n \]

代表转移过程中的关键元素。对于相邻的 \(x_k, x_{k+1}\)，我们要求

\[ b_{x_k} \le b_{x_{k+1}}, \]

它们之间的贡献为：

\[ \min_{y_k} \left( x_{k+1} - x_k - 1 + \sum_{i=x_k}^{y_k} [b_i < b_{x_k}] + \sum_{i=y_k+1}^{x_{k+1}} [b_i > b_{x_{k+1}}] \right). \]

通过调整法可知，一定存在一组最优解使得

\[ b_{x_k+1} \dots b_{x_{k+1}-1} \]

中所有元素均

\[ \notin [b_{x_k}, b_{x_{k+1}}]. \]

所以说我们把前面 \(<b_{x_k}\) 的换成 \(<b_{x_{k+1}}\) 也没有关系！

因此令

\[ f_{i,j,t=0/1} \]

表示考虑 \(b_1 \dots b_i\)，\(i\) 的下一个关键元素为 \(x_{k+1} = j\)，\(w = [i > y_k]\) 的答案。

线段树上维护矩阵乘法标记即可做到 \(O(n \log n)\)。