KSN2021

给定一个长度为 \(N\) 字符集为 \(\{{\texttt?},{\texttt A},{\texttt B}\}\) 的字符串，求将每个 \(\texttt?\) 替换为 \(\texttt A\) 或 \(\texttt B\) 后可以得到多少个恰有 \(K\) 个长度为 \(M\) 只包含一种字符的子串。

\(N\leq 3000\)。

考虑 dp。记 \(f_{i,j,c}\) 为长为 \(i\) 的前缀，恰有 \(j\) 个只含一种字符的长为 \(M\) 的子串且结尾字符为 \(c\) 的填法数量。

不难想到枚举结尾的 \(c\) 连续段长度转移。注意到预处理出从每个位置往前可能最长的连续的 \(c\) 的长度后贡献形如矩阵中一列之和与斜对角线之和，可以使用前缀和优化，复杂度 \({\mathcal O}(n^2)\)。

\(N\times M\) 的网格图，第 \(i\) 行第 \(j\) 列的格子是黑色当且仅当 \(i\ \text{and}\ j = 0\)。\(Q\) 组询问子矩形内的黑色四连通块数量。

\(N,M\le 10^9,Q\le 10^5\)。

可以看到，放眼于无限大的平面，黑色格子所构成的图形具有以下特点：

• 是一颗树。
• 不存在 \((x,y),(x-1,y),(x,y-1)\) 同为黑色的情况。

有了这两个性质，我们可以断言：红色方框内的连通块数量即为 跨左、上两条边的黑色方格对数。使用数位 dp 求出，复杂度 \({\mathcal O}(Q\log n)\)。

\(N\) 个小球排成一行，球有颜色，每次可以向交互库询问区间内颜色数量。需要求出所有小球相对的颜色。记询问上限为 \(Q\)。

\(N\le 1000\)。

• 不超过 \(4\) 种颜色 / 不少于 \(N-1\) 种颜色 / 同种颜色编号连续，\(Q=2000\)。
• 无特殊限制，\(Q=10000\)。

数据分治。

不少于 \(N-1\) 种颜色 / 同种颜色编号连续：思博题。

无特殊限制：从前往后扫，假设进行到第 \(i\) 个球时，已经求出前 \(i-1\) 个球的情况。记 \(f(l,r)\) 为 \([l,r]\) 内颜色数，\(g(x)=[f(x,i-1)=f(x,i)]\)。注意到 \(g\) 取值具有单调性，而 \(f(x,i)\) 可以通过询问交互库得出，二分即可在不超过 \(\log N!\le \frac{1}{2}N\log N\) 次询问解决。

不超过 \(4\) 种颜色：维护每种颜色当前最靠右的位置，并对此二分。精细实现可以使询问数不超过 \(2N\)。

给定长为 \(N\) 的排列，每次操作可以将当前相邻的两数中删去较大者。求经过任意次操作后的序列个数。

\(N\le 3\times 10^5\)。

观察到性质：\((l,r)\) 能被删空意味着 \([l,r]\) 最小值等于 \(\min(a_l,a_r)\)。

令 \(f_i\) 表示以位置 \(i\) 为结尾的序列个数。根据上述性质容易写出转移并优化。具体地，用数据结构（比如 set）对于所有 \(i\) 维护出 \(p<i\) 满足 \(a_p<\min(a_{p+1},…,a_i)\) 的 \(p\) 所构成集合 \({\rm S}_i\)，则转移为 \(f_i=\sum_{j=\max \text{S}_i+1}^{i-1}f_j+\sum_{j\in \text{S}_i}f_j\)。复杂度 \({\mathcal O}(n\log n)\)。

给定长为 \(N\) 的序列 \(A,B\)。以此生成图 \(G\)：\(x\) 与 \(y\) 间有边当且仅当 \(A_x\oplus A_y>\max(A_x,A_y)\)。求每个点所属连通块的 \(B\) 值之和。

\(N\le 10^5,A_i<2^{31}\)。

从生成方式入手，不妨设 \(a<b\)，则 \(a\oplus b>\max(a,b)\) 等价于 \(b\) 在 \(a\) 的最高位为 \(0\)。

那么将点按 \(A\) 从大到小排序后扫一遍。如果将此前在当前最高位为 \(0\) 的点暴力连边复杂度难以接受，但是注意到最终的连通性必然形如：所有在此位为最高位且之前有点在此位为 \(0\) 的点 和 此位为 \(0\) 且此后有点以此为最高位的点 所构成的集合同属一连通块。记录下每一位的情况即可做到 \({\mathcal O}(n(\log n+\log V))\)。

二维平面，第 \(i\) 列有一座高度为 \(H_i\) 的山。你可以进行移动，每次移动可以 左上 / 右上 / 正上，耗费 \(4\) 代价；左下 / 右下 / 正下，耗费 \(1\) 代价；左 / 右，耗费 \(2\) 代价。两个个维度的移动距离均为 \(1\)。可以悬空，不能穿山。

\(Q\) 组询问，每次给定 \(S_i,T_i\)，问从 \(S_i\) 列的山峰移动到 \(T_i\) 列的山峰最少需要多少代价。

\(N,Q\le 2\times10^5\)。

不妨设 \(s<t\)，其路线必然形如上图。其中红色的上升段仅有 右 / 正上 / 右上，黄色的平行段仅有 右，蓝色的下降段仅有 右 / 正下 / 右下。分界点即为最大值最靠左和最靠右的位置。

贪心地选择，必然在红色和蓝色段尽量多的选择 右下 和 右上，因为这可以减少总的移动次数。怎样尽量多的选择？以红色段为例，我们考虑在最开始的时候抬升到一个位置，使得其可以持续向右上走直到达到黄色段的高度。如图：

由于不希望浪费步数，最优策略一定会如上图一样，使得这条斜线恰好切到某座山，那么抬升的高度即为 过这些点斜线的截距最大值 - 过起点斜线的截距，也即 \(\left(\max\limits_{i=s}^p(H_i-i)\right)-(H_s-s)\)，其中 \(p\) 为分界点位置。用 ST 表维护，复杂度 \({\mathcal O}(n\log n+Q)\)。由于要维护三个 ST 表（\(H_i\) / \(H_i+i\) / \(H_i-i\)），且需要知道最大值位置，代码会比较繁琐。