CF problems

多刷 CF，锻炼思维。

1987D（1800）

注意到 Alice 每一轮只会吃所有满足条件的蛋糕中最小的一个，并且只要她吃了同美味值的蛋糕中的一个，这个美味值的蛋糕就没用了，所以 Bob 想达到目的肯定要将同美味值的一组蛋糕全部吃掉。设 $f_{i,j}$ 表示当前考虑到第 $i$ 组蛋糕，当前 Bob 有 $j$ 的空闲时间的最小贡献。设 $c_i$ 表示美味值为 $i$ 的有多少个。转移：$f_{i,j}=\min\{f_{i+1,j+1}+1,f_{i+1,j-c_i}\}$，其中 $j \geq c_i$。时间复杂度 $O(n^2)$。好题。code

1981C（1800）

不妨设所有不等于 $-1$ 的 $a_i$ 组成序列 $\{c_k\}$， $[1,c_1]$ 和 $[c_k,k]$ 我们只要不断操作就行了，而 $[c_i,c_{i+1}]$，只要注意到在一棵二叉树上，节点 $i$ 的父节点编号正好是 $\lfloor\frac{i}{2}\rfloor$，那么我们的问题就转化为求节点数为 $V$ 的二叉树上 $c_i$ 到 $c_{i+1}$ 的长度为 $x$ 的路径。复杂度 $O(n\log V)$，实现上可能是 $O(n\log^2 n)$ 的。好题！也可以考虑每一次除以二相当于二进制表达扣掉末尾一位，乘二相当于二进制表达末尾加上一位，然后将问题转化。code

1979D（1800）

可以知道满足 $k-proper$ 的 01 串只可能是每 $k$ 个数相等，相邻的两组 $k$ 个数不相同。枚举 $p$，用字符串哈希判断字符串相等即可。不如前面两个题好。code

1656H（3200）

画风突变。设 $a_i=\prod\limits_{j=1}^{k_i} p_j^{\alpha_j}$，若 $\alpha_i > \max\limits_{x \in S_B} \{\log_p x\}$，那么 $a_i$ 就只能删掉了。定义 $v_p x$ 表示 $x$ 的质因数分解中 $p$ 的指数。则该条件可表示为：

$$\forall x \in S_A,\forall p,\exists y \in S_B,v_p x \leq v_p y$$

$$\iff \forall x\in S_A,\forall p,\exists y \in S_B,v_p x=\min(v_p x,v_p y)$$

$$\iff \forall x \in S_A,\forall p,\exists y \in S_B,v_p \frac{x}{\gcd(x,y)}=0$$

$$\iff \forall x \in S_A,\forall p,v_p( \gcd\limits_{y \in S_B} \frac{x}{gcd(x,y)})=0$$

$$\iff \forall x\in S_A \gcd_{y\in S_B}\frac{x}{\gcd(x,y)}=1$$

暴力判断显然过不了。考虑到我们的操作其实是求 $\gcd$，单点删除。对于每个 $a_i$ 和 $b_i$ 维护一颗 seg，对于 $a_i$ 的这棵 seg，每编号为 $j$ 的叶节点维护 $\frac{a_i}{\gcd(a_i,b_j)}$，单点删除就相当于把这个点的值改为 $0$。复杂度 $O(n^2 \log n \log V)$，其中 $\log V$ 是 $\gcd$ 的复杂度，用 pbds 可能能把这个消掉。code

1994E（2000）

显然 $k=1$ 时的答案就是这棵树的节点数。我们可以通过砍叶子结点的方式得到 $1$ 到 $siz$ 的所有数值。问题就变成了如何选数，也就是 $ans$ 需要这个 $siz$ 的哪几位做出贡献。一位一位考虑就可以了。只要想通前两句话，这个题就很好写。诈骗题。code

13E（2700）

弹 飞 绵 羊。code

616E（2200）

最主要的是整除分块的结论及其证明。

$$\sum\limits_{k=1}^m n \bmod k = \sum\limits_{k=1}^{m} (n-k\lfloor\frac{n}{k}\rfloor)=nm-\sum\limits_{k=1}^m k\lfloor\frac{n}{k}\rfloor$$

方便起见，我们设 $f(x)=\lfloor\frac{n}{x}\rfloor$。

对于右面这一坨整除分块。注意到 $f(k)$ 的下降是阶梯状的，我们考虑对于每个阶梯的值算出来再乘上这一段区间内 $k$ 的和就可以了。对于 $i,j$，如果 $f(i)=f(j)$，则 $j$ 的最大值是 $f(f(i))$。

证明

设 $k=f(i)$，可知 $k \leq \frac{n}{i}$。可推出：

$$f(k)\geq f(f(i))=\lfloor i \rfloor=i$$

故 $j$ 取 $\max$ 时 $\forall i$ 满足条件，$i=i_{\max}=f(k)=f(f(i))$。$\square$

于是我们就可以在 $O(\sqrt n)$ 的时间内完成求和。code

1045G（2200）

紫色的 2200。三维偏序问题的变形。将坐标离散化，搞出坐标左右端点在离散化结果上对应的区间，注意到 $i,j$ 两个人能互相看到条件是（不妨设 $x_i \geq x_j$）：

$$\left\{ \begin{aligned} x_i-r_i \leq x_j \cdots (1) \\ x_j+r_j \geq x_i \cdots (2) \\ |q_i-q_j| \leq k \cdots (3) \end{aligned} \right.$$

结合 (1)(2) 式，可得

$$x_i-r_j \leq x_j \leq x_i-r_i$$

可推出 $r_i \leq r_j$。

考虑将 $r$ 作为三维偏序中的一维，将 IQ 值作为另一维，$x$ 值作为第三维，我们以 $r$ 排序，分治过程中对左右两端。这里顺便写一下 CDQ 分治的思想和方法。

CDQ 分治主要解决关于点对的问题，是离线做法。递归求解区间 $(l,r)$ 上包含的点对时，将 $(l,r)$ 拆成 $(l,mid)$ 和 $(mid+1,r)$ 两段，对于 $i,j \in [l,mid]$，递归求解；对于 $i,j \in (mid,r]$，递归求解；对于 $i \in [l,mid],j \in (mid,r]$，单独设计算法求解。伪代码：

solve(l,r){
	mid=(l+r)/2
	solve(l,mid),solve(mid+1,r)
	solve the third situation
}

1228E（2300）

容斥。先讲原理。对于 $n$ 个集合 $S_1,S_2,\dots,S_n$，我们有：

$$|\bigcup\limits_{i=1}^n S_i|=\sum\limits_{m=1}^n (-1)^{m-1} \sum\limits_{a_i\le a_{i+1}}|\bigcap\limits_{i=1}^m S_{a_i}|$$

$$|\bigcap\limits_{i=1}^n S_i|=|U|-|\bigcup\limits_{i=1}^n \bar{S_i}|$$

其中 $a$ 是 ${x\in \mathbb Z|1\leq x\leq n}$ 的一个子集。可以通过 $n=3$ 的情况来类比得到证明。

回到这个题。我们考虑每一行合法的情况数就是 $k^n-k^{n-1}$。正难则反，我们考虑让列不合法。情况数就是分别选 $1$ 到 $n$ 列，让他们不合法,选 $i$ 列不合法的情况数是：

$$(k-1)^i(k^{n-i}-(k-1)^{n-i})=(k-1)^ik^{n-i}-(k-1)^n$$

有因为每一列的情况是等价的，所以总情况数就只用取个 $n$ 次方，乘上 $n \choose i$，这就是容斥公式中的 $\sum\limits_{a_i\le a_{i+1}}|\bigcap\limits_{i=1}^m S_{a_i}|$ 部分，然后我们套公式就可以得到答案是：

$$\sum\limits_{i=0}^n (-1)^i C_n^i ((k-1)^ik^{n-i}-(k-1)^n)^n$$

然后就可以了。代码很短。code

1787H（3300）

答案最优就是损失最少。由题意，我们有：

$$Ans=\sum_{i=1}^n \max\{b_i-k_i\cdot t,a_i\}=\sum_{i=1}^n b_i -\sum_{i=1}^n \min\{k_i \cdot t,b_i-a_i\}$$

记 $c_i=b_i-a_i$，则 $Ans=\sum_{i=1}^n b_i -\sum_{i=1}^n\min\{k_i\cdot t,c_i\}$。如果我们钦定一部分题目花费 $c_i$ 的代价，则剩下的题目应当贪心地将 $k_i$ 降序排列（排序不等式）。设 $f_{i,j}$ 表示 $i$ 个数中钦定 $j$ 道题得 $k \cdot t $ 的最小代价，有转移：

$$f_{i,j}=\left\{ \begin{aligned} f_{i-1,j}+c_i & & j=0 \\ \min\{f_{i-1,j}+c_i,f_{i-1,j-1}+k_i\cdot j\} & & j>0 \end{aligned} \right.$$

时间复杂度是 $O(n^2)$ 的，考虑在转移过程中优化。打个表发现 $f_{i,j}$ 关于 $j$ 是凸的（你问我怎么想到的，汪娟会告诉你，这就是你与 CF rating 3300 的区别）。于是我们设 $g_{i,j}$ 表示 $f_{i,j}-f_{i,j-1}$，然后用它改写 DP 式子得到：

$$f_{i,0}+\sum_{k=1}^j g_{i,k}=\min\{f_{i-1,0}+\sum_{k=1}^j g_{i-1,k}+c_i,f_{i-1,0}+\sum_{k-1}^{j-1}g_{i-1,k}+k_{i}\cdot j\}$$

$$\iff c_i+\sum_{k=1}^j g_{i,k}=\sum_{k=1}^{j-1}+\min\{g_{i-1,j}+c_i,k_{i,j}\}$$

我们发现上式的元太多了，于是我们将上式记为（1）式。然后用 $j-1$ 代替 $j$ 后改写上式，得：

$$c_i+\sum_{k-1}^{j-1}g_{i,k}=\sum_{k=1}^{j-2}g_{i-1,k}+\min\{g_{i-1,j-1}+c_i,k_{i,j-1}\}$$

将上式记作（2）式，用（1）式减（2）式，得：

$$g_{i,j}=g_{i-1,j-1}+\min\{g_{i-1,j}+c_i,k_{i}\cdot j\}-\min\{g_{i-1,j-1}+c_i,k_i \cdot (j-1)\}$$

$k$ 是不增的。注意到 $g_{i,j}-g_{i,j-1} \geq k_i$，接下来我们尝试证明这个性质。

对 $g_{i,j}-g_{i,j-1}\geq k_i$ 的证明

运用数学归纳法。

当 $i=2$ 时，结论显然成立；

若 $i=i$ 时成立，则，当 $i=i+1$ 时，有：

观察 $\min\{g_{i,j}+c_i,k_i \cdot j\}$ 这一项，发现 $\Delta g_{i,j}\geq \Delta k_i \cdot j$，则存在一个 $pos$ 使 $\forall j \leq pos,g_{i,j}\leq k_i\cdot j,\forall j \geq pos,g_{i,j} \geq k_i \cdot j$，则由 $g_{i-1}$ 变换到 $g_i$ 的过程如下：$j \le pos$ 的位置不变。$j \ge pos$ 的位置的值加 $k_i$ 。中间插入 $k_i \cdot j - c_i$。

于是我们只用考虑中间位置与其左右两边的差就可以了。

$$g_{i-1,pos} \ge k_i \cdot pos - c_i$$

$$g_{i,pos-1} = g_{i-1,pos-1} \le k_i \cdot (pos-1) - c_i$$

$$g_{i,pos} = k_i \cdot pos - c_i$$

$$g_{i,pos+1} = g_{i-1,pos} + k_i$$

可证明

$$g_{i,pos+1} - g_{i,pos} = g_{i-1,pos} + k_i - k_i \cdot pos + c_i \ge k_i$$

$$g_{i,pos} - g_{i,pos-1} = k_i \cdot pos - c_i - g_{i-1,pos-1} \ge k_i$$

$$\square$$

由此我们可以找到一个位置 $pos$ 使得 $\forall j \leq pos,g_{i,j}\leq k_i\cdot j,\forall j \geq pos,g_{i,j} \geq k_i \cdot j$。于是从 $g_{i-1}$ 推到 $j_{i}$ 就变得简单了起来。我们用平衡树维护 $g_i$，就可以把时间复杂度做到 $O(n\log n)$。这种在斜率上操作的方法叫 Slope Trick。code

1187E（2100）

换根 DP 好题。首先我们注意到最后的结果在我们选出第一个填黑色的节点的时候就已经确定了，于是我们设 $g_i$ 表示 $i$ 为第一个填黑色的节点时的答案，直接求 $g_i$ 不是很方便，于是我们考虑设 $f_i$ 表示选了 $i$ 后其子树对答案的贡献。可得 $f_i=siz_i+\sum_{j \in son\{i\}}f_j$，得到 $g_1=n+\sum_{\{j,1\}\in E}f_j$，如果每次都求一遍复杂度为 $O(n^2)$，考虑换根 DP。先求出 $g_1$，然后考虑 $g_i$ 的递推式，这玩意显然要自上向下推，设 $i=fa_j$，易得（虽然我得来并不易） $g_j=n+(n-siz_j)+\sum_{k \in son\{i\},k \neq j}f_k+\sum_{k \in son\{j\}}f_k$，稍微推一推，得 $g_j=g_{i}-2siz_j+n$，然后就 $O(n)$ 地过掉了。code

506D（2400）

先考虑暴力，每次枚举颜色，在查询的时候如果两点只用同一种边就能联通，那么这个颜色对答案贡献加一，维护联通用并查集，时间复杂度 $O(qm\log n)$，在颜色数很小的时候可以过。再考虑另一种暴力，先对每一种颜色分别建图，然后枚举这上面的每个点对查询，如果联通则贡献加一，时间复杂度 $O(mn^2\log n)$，在 $n^2<q$ 的时候会比前一种情况优。

接下来考虑如何优化，这里使用根号分治。注意到如果当前颜色的边数小于 $\sqrt m$ 的时候，这样所有这样的颜色的连通块的点的总数的平方和不超过 $n\sqrt n$，于是可以用第二种暴力，时间复杂度 $O(n\sqrt n \log n)$；如果当前颜色边数大于 $\sqrt m$，那么满足这个条件的颜色数最多 $\sqrt m$，故使用第一种暴力，时间复杂度 $O(\sqrt m q\log n)$，加一块，稳稳过。code

809C（2600）

先把 $a$ 的表打出来。

 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
 2  1  4  3  6  5  8  7 10  9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31
 3  4  1  2  7  8  5  6 11 12  9 10 15 16 13 14 19 20 17 18 23 24 21 22 27 28 25 26 31 32 29 30
 4  3  2  1  8  7  6  5 12 11 10  9 16 15 14 13 20 19 18 17 24 23 22 21 28 27 26 25 32 31 30 29
 5  6  7  8  1  2  3  4 13 14 15 16  9 10 11 12 21 22 23 24 17 18 19 20 29 30 31 32 25 26 27 28
 6  5  8  7  2  1  4  3 14 13 16 15 10  9 12 11 22 21 24 23 18 17 20 19 30 29 32 31 26 25 28 27
 7  8  5  6  3  4  1  2 15 16 13 14 11 12  9 10 23 24 21 22 19 20 17 18 31 32 29 30 27 28 25 26
 8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9 24 23 22 21 20 19 18 17 32 31 30 29 28 27 26 25
 9 10 11 12 13 14 15 16  1  2  3  4  5  6  7  8 25 26 27 28 29 30 31 32 17 18 19 20 21 22 23 24
10  9 12 11 14 13 16 15  2  1  4  3  6  5  8  7 26 25 28 27 30 29 32 31 18 17 20 19 22 21 24 23
11 12  9 10 15 16 13 14  3  4  1  2  7  8  5  6 27 28 25 26 31 32 29 30 19 20 17 18 23 24 21 22
12 11 10  9 16 15 14 13  4  3  2  1  8  7  6  5 28 27 26 25 32 31 30 29 20 19 18 17 24 23 22 21
13 14 15 16  9 10 11 12  5  6  7  8  1  2  3  4 29 30 31 32 25 26 27 28 21 22 23 24 17 18 19 20
14 13 16 15 10  9 12 11  6  5  8  7  2  1  4  3 30 29 32 31 26 25 28 27 22 21 24 23 18 17 20 19
15 16 13 14 11 12  9 10  7  8  5  6  3  4  1  2 31 32 29 30 27 28 25 26 23 24 21 22 19 20 17 18
16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
18 17 20 19 22 21 24 23 26 25 28 27 30 29 32 31  2  1  4  3  6  5  8  7 10  9 12 11 14 13 16 15
19 20 17 18 23 24 21 22 27 28 25 26 31 32 29 30  3  4  1  2  7  8  5  6 11 12  9 10 15 16 13 14
20 19 18 17 24 23 22 21 28 27 26 25 32 31 30 29  4  3  2  1  8  7  6  5 12 11 10  9 16 15 14 13
21 22 23 24 17 18 19 20 29 30 31 32 25 26 27 28  5  6  7  8  1  2  3  4 13 14 15 16  9 10 11 12
22 21 24 23 18 17 20 19 30 29 32 31 26 25 28 27  6  5  8  7  2  1  4  3 14 13 16 15 10  9 12 11
23 24 21 22 19 20 17 18 31 32 29 30 27 28 25 26  7  8  5  6  3  4  1  2 15 16 13 14 11 12  9 10
24 23 22 21 20 19 18 17 32 31 30 29 28 27 26 25  8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9
25 26 27 28 29 30 31 32 17 18 19 20 21 22 23 24  9 10 11 12 13 14 15 16  1  2  3  4  5  6  7  8
26 25 28 27 30 29 32 31 18 17 20 19 22 21 24 23 10  9 12 11 14 13 16 15  2  1  4  3  6  5  8  7
27 28 25 26 31 32 29 30 19 20 17 18 23 24 21 22 11 12  9 10 15 16 13 14  3  4  1  2  7  8  5  6
28 27 26 25 32 31 30 29 20 19 18 17 24 23 22 21 12 11 10  9 16 15 14 13  4  3  2  1  8  7  6  5
29 30 31 32 25 26 27 28 21 22 23 24 17 18 19 20 13 14 15 16  9 10 11 12  5  6  7  8  1  2  3  4
30 29 32 31 26 25 28 27 22 21 24 23 18 17 20 19 14 13 16 15 10  9 12 11  6  5  8  7  2  1  4  3
31 32 29 30 27 28 25 26 23 24 21 22 19 20 17 18 15 16 13 14 11 12  9 10  7  8  5  6  3  4  1  2
32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

打表程序：

int a[105][105],arr[205];
std::set<int> se;
int main(){
	freopen("a.txt","w",stdout);int n=32,m=32;a[1][1]=1;
	for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){
			if(i==1&&j==1){continue;} se.clear();
			for(int k=1;k<i;k++)se.insert(a[k][j]);
			for(int k=1;k<j;k++)se.insert(a[i][k]);
			int cnt=0; a[i][j]=-1;
			for(auto x:se)arr[++cnt]=x;
			if(arr[1]>1)a[i][j]=1;
			else{for(int k=2;k<=cnt;k++){if(arr[k-1]+1!=arr[k]){a[i][j]=arr[k-1]+1;break;}}}
			if(a[i][j]==-1)a[i][j]=arr[cnt]+1;
		}
	}for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]<10)std::cout<<" "<<a[i][j]<<" ";
			else std::cout<<a[i][j]<<" ";
		}std::cout<<"\n";
	}
}

然后发现对于每一个大小为 $2^k$ 的正方形（下文简称“$k$ 正方形”）区域都均分成了四块，每一行、每一列都填满了 $1$ 到 $2^k$ 的排列（性质 1），并且左上角和右下角一样，右上角和左下角一样，都是左上角对应位置的数字加上 $2^{k-1}$（性质 2）。

对于矩形 $(n,m)$ 的询问，我们找最小的一个可以包住它的 “$k$ 正方形”。注意到 $a$ 关于主对角线轴对称，所以不妨设 $n\geq m$，这样讨论矩形在 $k$ 正方形中的位置。

如果 $(n,m)$ 在右下角，我们把 $k$ 正方形分成四个 $k-1$ 正方形，然后根据性质 1，我们可以利用求和公式求出要求的矩阵中左上角、右上角、左下角的和，对于右下角我们递归求解。

如果 $(n,m)$ 在右上角，左边那一块可以用求和公式求出，右半边递归求解，注意要加上 $2^{k-1}$ 的偏移量。

这样就可以 $O(可过)$ 了。code

1891F（2000）

正 难 则 反。code

837D（2100)

先设 $f_{i,j,x,y}$ 表示 $i$ 个数，选了 $j$ 个，其中 $x$ 个 2，$y$ 个 5，是否可行。注意到不可过，于是将 $x$ 这较大的一位放到结果，这相当于是某些题里把较小的答案放到状态里的反过程。设 $f_{i,j,x}$ 表示 $i$ 个数，选了 $j$ 个，其中 $x$ 个 5 的时候最多多少个 2，得到转移 $f_{i,j,x} = \max\{f_{i-1,j-1,x-c5(i)},f_{i-1,j,x}\}$，压维，后两维倒叙就过了。code

1718A2（1900）

我们显然可以通过 $n$ 次异或 $a_i$ 来通过 $n$ 的代价来把 $a_i$ 全变成 $0$，注意到如果一个长度为 $len$ 的区间异或和是 $0$，则这个区间定可以通过 $len-1$ 的次数变成零，于是我们只需要统计这样的区间的个数，然后减掉这样的区间数就行了。code

359D（2000）

注意到 $\exists k\in [l,r], \forall i\in [l,r], a_k|a_i \iff \min(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,a_{l+1},\dots,a_r)$，于是二分区间长度，线段树维护 $\min$ 与 $\gcd$ 就行了。code

2040C（1600）

神秘题，场上被创飞了，从第一步就没想出来，但只要想到第一步问题就迎刃而解了。我们先考虑这个排列的生成方式。注意到我们只需要从 $1$ 到 $n$ 考虑填的位置（以上两句话我硬生生没想到，以后可以当做一个思维角度），于是发现每次这个数必然填在空白字符段的两端，这样每一个数都能做出最大贡献。于是我们发现一共有 $2^{n-1}$ 种满足 $S(p)$ 最大的排列。我们用一个二进制数来表示每一个数都放在了前端还是后端，于是我们发现这个二进制数正好对应着排名，于是把排名拆位就行了。code

622F（2600）

引理：设 $f_k(x)=\sum_{i=1}^n i^k$，我们有 $\deg f_k(x)=k+1$。

证明：这里对 $k$ 使用数学归纳法。

当 $k=1$ 时，$f_1(x)=\sum_{i=1}^x i = \frac{x(x-1)}{2}$，$\deg f_1(x)=2$，成立；

如果当 $k=n$ 时，$\deg f_{n}(x) = n+1$；

那么当 $k=n+1$ 时，$f_{n+1}(x)=f_n(x)\cdot f_{1}(x)-g(x)$，其中 $\deg g(x) < n+1$，故 $\deg f_{n+1}(x)=\deg f_{n}(x)\cdot f_{1}(x)=n+1$，于是引理得证。

于是我们知道了 $f_{k}(x)$ 的度数，这启发我们可以通过选择 $k+2$ 个点来确定 $f_k(x)$，然后利用拉格朗日插值法求出 $f_k(n)$。下面简记 $f_{k}(x)$ 为 $f(x)$。

我们考虑选 $x=1,2,\dots,k+2$ 的这些点，由拉格朗日插值，我们有

$$f(n)=\sum_{i=1}^{k+2}y_i\prod_{j\in [1,i)\bigcup(i,n]}\frac{n-j}{i-j}$$

发现分子分母都可以预处理，于是 $O(K)$ 直接过。code

785E（2200）

注意到交换 $a_i,a_j$ 之后，相较之前的答案，如果 $a_i<a_j$，$ans+1$，否则 $ans-1$，然后 $[1,i)$ 对答案的影响与 $(j,n]$ 对答案的影响没有任何变化，$(i,j)$ 能使 $ans$ 加上两倍的小于 $a_j$ 的数量再减去两倍的小于 $a_i$ 的数量，分块维护小于 $k$ 的数量就完了。code

1558D（2600）

难度：2600。

仙品。注意到题目相当于告诉我们 $m$ 组大小关系，让我们求可能的排列个数。如果我们知道小于号的个数 $c$，那么使用插板法可得答案就是 $C_{2n-c-1}^n$，于是问题转化为求 $c$。我们维护一个集合 $S$，存储所有的前面是小于号的数，答案就是 $\# S$，于是考虑一个条件 $a_i<a_j$ 时，如果 $j$ 不在 $S$ 中，也就是说 $a_j$ 前面是 $\le$，那就把 $j+1$ 插进去，并且把 $S$ 中所有比 $j$ 大的数加一。我们考虑如何用一个 DS 维护集合 $S$，也就是说这个 DS 需要维护插入和区间加，于是想到平衡树。code

420D（2200）

难度：2200，洛谷蓝

反着考虑就完了。code

2013E（2200）

难度：2200

首先前缀 $\gcd$ 是单调不升的，我们尽量在前面下降，然后降到 $\gcd(a_1,\dots,a_n)$，然后直接停下，这样贪心就是对的，并且复杂度是 $O(n\log n)$ 的，因为每一次下降最少降为原来的 $\frac{1}{2}$，所以 $n\log n$ 一般情况下跑不满，这样就过了。code

1301F（2600）

难度：2600

很自然地想到把颜色相同的点缩起来跑 Floyd，预处理原来的点不通过传送到缩起来后的点的距离，然后每次询问枚举第一次和最后一次在那个颜色传送，时间复杂度 $O(nmk+qk^2)$，但是 $qk^2$ 太大了。于是考虑直接搞点可以经过传送到某个颜色的距离，这个对每个颜色跑一遍 bfs 就行了。记 $d(i,x,y)$ 表示点 $(x,y)$ 到颜色为 $i$ 的点们的距离，答案就是起点与终点间曼哈顿距离与

$$\min_{c=1}^k\{d(c,r_1,c_1)+d(c,r_2,c_2)+1\}$$

取 $\min$ 的结果。时间复杂度 $O(k(nm+q))$，稳稳过。code

2078D（1800）

difficulty:1800

STO Wei_Han ORZ

从前往后看问题，发现问题具有后效性，没法 DP，折半也是不行的因为我们并不能很好地合并前后两端的答案，于是正难则反，考虑反着做，发现这样就没有后效性，只用考虑后几位的答案就行了。

再求值之前，我们先做一些操作。我们将左边的门编号为 $0$，右边的门编号为 $1$，我们设 $a_{i,o}$ 表示第 $i$ 关编号为 $o$ 的门做乘法操作的倍数，如果是加法门，就令 $a_{i,o}=1$，然后另计 $b_{i,o}$ 表示加上的数。。我们设 $f_{i,o}$ 表示考虑到第 $i$ 个关卡左/右边的门对前面的决策产生的贡献。易知对于当前一个门，加法门所产生的贡献并不会对前面造成什么影响，而对于每个门产生的贡献，把这些贡献全部放到能产生更大贡献的那一边要比留一些在更劣的一边优，于是我们得到递推式

$$f_{i,o}=f_{i+1,o}+(a_{i,o}-1)\max(f_{i+1,0},f_{i+1,1})$$

并且如果当前出现加法门，则使

$$ans\leftarrow ans+b_{i,o}\max(f_{i+1,0},f_{i+1},1)$$

并且在最后给答案加上 $f_{1,0}+f_{1,1}$，时间复杂度 $O(nT)$，好奇为什么 $n$ 要放这么小。code

2092E（2100）

difficulty:2100

hint:对于有偶数个相邻块的块，它自己啥颜色对答案有关吗？

没有关！所以只用考虑边边上的就行了。然后就做完了。code

1716D（2000）

difficulty: 2000

定义 $f_{i,j}$ 表示第 $i$ 个点被地第 $j$ 次走到的方案数。列转移是容易的，但是转移复杂度太高。

考虑 $j$ 这一位，发现它并不是 $O(n)$ 的，而是 $O(\sqrt n)$ 的，所以可以暂且不管这一维。然后就可以前缀和优化直接做了。代码我没写。

2091G（2300）

difficulty: 2300

定义 $f_{i,j}$ 表示走 $j$ 步能否到达 $i$，转移容易列出，但 $i$ 的规模太大了，一些特殊的性质。发现当 $s>k^2$ 的时候，两次一定可以，于是 $i$ 的规模就变成了 $10^6$，但这还是过不了，并且发现想不动了，于是挂个 bitset 就行了。

OI 中可以使用的动态 bitset: https://codeforces.com/blog/entry/129454

1091E（2400）

difficulty：2400

抽象没边了。

hint：链接最有效的一集。

Erdős–Gallai 定理：对于一个序列 $d_1,d_2,\dots,d_n$，它可以成为一个简单无向图的度数的序列：等价于

1. $2|(\sum d)$;

2. $\forall k\in \{1,2,\dots,n\},\sum_{i=1}^k d_i\leq k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$。

对于 1，考虑每条边的贡献即可；对于 2，右边前一个式子是内部的，第二个式子是内部和外部的。

利用这个定理的朴素做法就是枚举 $d_{n+1}$，判断是否可行，时间复杂度 $O(n^2)$。

尝试寻找性质，观察阳历发现，如果 $d_{n+1}$ 是 $x$ 或 $y$ 时满足条件，那么对于所有 $x<z<y$ 且 $z$ 与 $x,y$ 奇偶性相同，$d_{n+1}=z$ 也是可以的。

于是将原序列排序，然后二分上下界。check 的时候考虑把当前值插入序列并保证序列单调性的位置就行了。时间复杂度 $O(n\log n)$。code

1149D（3000）

difficulty: 3000

称边权为 $a$ 的边为轻边，其余称为重边。我们发现去掉重边之后剩下的可以构成几坨连通块，并且如果一条路径在最小生成树上，那么它只会进出一个连通块最多一次。于是在连通块上 dp。设 $f_{S,u}$ 表示当前走过的连通块的集合为 $S$，当前走到点 $u$ 的最短距离。由于 $f_{S,u}$ 可以转移到 $f_{S,v}$ 意味着反过来也是可以的，所以需要用最短路的方式 dp，时间复杂度 $O(2^nm\log(2^nm))$，考虑优化。然后注意到对于 $siz\leq 3$ 的连通块不需要考虑，因为走内部边总一进一出快，于是时间复杂度 $O(2^{n/4}m\log(2^{n/4}m))$。code

1764H（3400）

difficulty: 3400

倒着做，考虑维护 $t$ 表示每个位置上的数最多能活多久，然后每次操作相当于对 $(l\dots r]$ 上的点区间覆盖，对 $l$ 上的点，$t_l\leftarrow \max_{x=l+1}^rt_x$，其连续段个数综合是 $O(n)$ 的，于是可以用 set 维护连续段，时间复杂度 $O(n\log n)$，同时用树状数组数点，当前的答案就是 $t_i>x+k-1$ 的位置。code

2134D

difficulty: unknown

注意到一次滑行操作最多使直径加 1，所以我们的方法要尽量让每次操作都加 1，发现这是可行的，只需要找出一条边 $(u,v)$ 满足 $u$ 在直径上而 $v$ 不在，令 $u$ 在直径上的前驱为 $f$，那么 $a=f,b=u,c=v$ 滑动一次就行。