兵棋

idea,solution,data,std by zhoukangyang

这题有很多做法，欢迎大家在评论区交流。

考虑设 $t_i$ 表示 $i$ 被删除的时间。

考虑从前往后依次确定 $t_i$。如果 $i$ 时刻在 $t_i$ 时刻被删掉，那么 $i$ 前面的第一个 $\ge t_i$ 的 $t$ 上的字符一定和 $i$ 不同。而 $t_i$ 是满足条件的值中最小的一个。

所以可以考虑对于每个 $j$ 记录 $i$ 前面第一个（下标最大的一个）满足 $t_{pos}\ge j$ 的 $s_{pos}$。

考虑记录该字符串。初始状态就是整个字符串均为 $s_1$。

加入位置 $i$ 的时候，修改即为在字符串中找到第一个 $\ne s_i$ 的字符 $p$，将其修改为 $s_p$。如果找不到则说明该位置不会被删除。

直接用动态规划维护是 $\mathcal{O}(n{2}^k)$ 的。

注意到我们其实只关心字符串中 $1$ 的个数！这样就能做到 $\mathcal{O}(nk)$ 了。

思考题：如果 $s_1$ 也会被删除该怎么做？（这题也能做到 $\mathcal{O}(nk)$。）

难度查找

idea,solution,data,std by zhoukangyang

致歉

本来这题是 $n\times n$ 矩阵找第 $n$ 小，只允许比较，要求次数 $\mathcal{O}(\sqrt{n})$，放 Day2T3 的。

但是后来因为常数太大，卡不掉暴力，就改成了现在这个版本。

结果这题之前在一些地方的模拟赛里面出现过了，赛前没有查到一样的题，向大家道歉！！

题解

考虑提取所有偶数列，然后求出其中第 $(k-n)/2$ 小值。我们发现最后的答案一定大于等于这个值，所以前 $k$ 小的元素中我们已经确定出了 $(k-n)/2\times 2$ 个了，还差 $n$ 个。

现在我们只需要接下来再取出 $n$ 个元素即可。这个可以把每行第一个没被选的元素丢到 priority_queue 实现。

行列交替地做，操作次数是 $T(n,m)=T(m,n/2)+2n$，有 $T(n,n)=6n$，还不能通过（然而数据较弱，部分选手直接实现了这个算法也通过了）。

我们发现如果 $(x-1,y)$ 和 $(x,y-1)$ 还没被选进前 $k$ 小，$(x,y)$ 就暂时不会被选。事实上，加上这个优化操作次数就是 $5n$ 的了。

我们证明从 $T(n/2,n/2)$ 的答案推到 $T(n,n)$ 的过程中我们最多只会问 $2.5n$ 次。

证明：考虑 $T(n/2,n)$ 到 $T(n,n)$ 的过程。设第 $i$ 行刚开始去了 $a_i$ 个元素（$a_i$ 是偶数），最终取了 $b_i$ 个元素，那么最终我们会问 $n+|\{b_i\}|$ 次。在 $T(n/2,n/2)$ 中，我们询问了 $n/2+|\{a_i\}|$ 次。；

我们先假装总询问次数是 $3n/2+n+|\{a_i\}|$ 次，接下来观察我们会在什么情况下少问一些。

在做 $T(n/2,n)$ 时，如果 $a_i\ne a_{i-1}$，那么 $(i,a_i+2)$ 一定被问过了。

此时，如果 $a_i\ne b_i$，那么我们就利用上了 $(i,a_i+2)$ 的信息，询问次数 $-1$；而如果 $a_i=b_i$，那么 $b_i$ 中一定不会出现 $a_i+1$ 这个数，询问次数 $-1$。

综上，我们一定少询问了 $|\{a_i\}|$ 次，也就是说我们只会询问 $5n/2$ 次。所以总询问次数不会超过 $T(n,n)=T(n/2,n/2)+5n/2$，即 $T(n,n)=5n$。

大海的深度

idea,solution,data,std by Kubic

$O(n{\log }^{2}n)$

分治。处理所有跨过分治点的贡献。只需 $O(\log n)$ 代价即可转化到原问题。

离线，扫描值域。令当前扫描到 $x$。对于每个 $i$，维护 $p_i$ 表示第 $i$ 时刻分治中心左边距离中心最近的 $\le x$ 的数的距离，$q_i$ 表示右边的距离。

$x$ 增大时对 $p,q$ 的修改均为区间取 $min$，用 $\text{segbeats}$ 维护即可。

还需要维护每个时刻的答案 $w_i$。第 $i$ 时刻 $min\ge x$ 的区间数量即为 $p_i\times q_i$。因此 $x$ 增大时，需要令 $w_i\leftarrow w_i+p_i\times q_i$。

每个 $i$ 处维护四维向量 $(p_i,q_i,p_i\times q_i,w_i)$，用矩阵表示修改即可。时间复杂度为 $O(n\log n)$。

加上外层分治，总时间复杂度为 $O(n{\log }^{2}n)$。

$O(n\sqrt{n})$

可以把要求的东西转化为 $\sum _{i=1}^n(su{f}_i-i)(i-pr{e}_i)a_i$。

其中 $pr{e}_i$ 表示 $i$ 前面第一个 $<a_i$ 的位置，$su{f}_i$ 表示 $i$ 后面第一个 $\le a_i$ 的位置。

考虑询问分块，将 $B$ 个询问分入同一个块中。

在进入每个块之前先将这个块中所涉及到的 $B$ 个位置设为 $+\mathrm{\infty }$，然后计算 $pre$ 和 $suf$。

此时序列被这 $B$ 个位置分为了 $O(B)$ 段。

对于一个询问，我们分析填上这 $B$ 个位置的数对 $pre$ 和 $suf$ 的影响。只考虑 $pre$，$suf$ 的分析是类似的。

可能有一些 $pre$ 会变为这 $B$ 个位置之一。每个段内只有所有非严格前缀最小值的 $pre$ 可能改变。

我们用类似于求 $pre$ 的过程，对这 $B$ 个位置以及每个段内的最小值做单调栈。

到达一个段时，我们可以用当前的单调栈刻画出这个段中所有数的 $pre$ 的变化情况：对于一个当前段中的前缀最小值 $a_i$，我们找到单调栈中第一个 $<a_i$ 的数 $a_t$。如果 $t$ 是 $B$ 个位置之一，那么 $pr{e}_i$ 会变为 $t$，否则 $pr{e}_i$ 不变。

于是我们可以把一次询问转化为在序列上的 $O(B^2)$ 次询问，每次询问一个段中有多少个 $\le w$ 的数。

这样做的时间复杂度为 $O({\displaystyle \frac{n^2}{B}}+n{B}^2)$，取 $B=n^{\frac{1}{3}}$ 可以得到 $O(n^{\frac{5}{3}})$ 的时间复杂度。

但我们可以进一步优化，可以发现，单调栈中有很多不变的数，我们可以在单调栈改变的时候将后面的数因为这次改变所产生的贡献全部计算出来。每次询问形如在第 $x$ 个段及之后的所有数中有多少个 $\le w$ 的数。

因为段只有 $O(B)$ 个，并且询问的 $w$ 也只有 $O(B)$ 种，所以我们可以用在每个段内双指针，并用二维前缀和预处理出每一种可能的询问的答案。

这 $O(B)$ 个点的贡献容易在过程中同时进行计算，这里不再赘述。

这样做的时间复杂度为 $O({\displaystyle \frac{n^2}{B}}+nB)$，取 $B=n^{\frac{1}{2}}$ 可以得到 $O(n\sqrt{n})$ 的时间复杂度。