这是本文档旧的修订版！
补题情况
| 题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
|---|---|---|---|
| A | 0 | 0 | 0 |
| B | 2 | 0 | 0 |
| C | 0 | 0 | 0 |
| D | 0 | 0 | 0 |
| E | 0 | 0 | 0 |
| G | 0 | 0 | 0 |
| J | 2 | 0 | 0 |
| K | 0 | 0 | 0 |
题解
B. xay loves monotonicity
题意
给定一个序列 $A$ 和序列 $B$，其中 $0\le b_i\le 1$ 接下来三种操作：
- $a_i\gets t$
- 对 $l\le i\le r$，$b_i\gets b_i\oplus 1$
- 给定 $l,r$。选取最长下标序列 $l\le i_1\le i_2\le \cdots i_k\le r$，满足 $a_{i_1}\le a_{i_2}\le\cdots \le a_{i_k}$，且对任意 $i_t\lt j\lt i_{t+1}$ 有 $a_j\lt a_{i_t}$。
对每个操作 $3$，输出 $b_{i_t}\neq b_{i_{t+1}}$ 的个数。
题解
设 $ma(L,R)=\max(a[L\sim R]),mb(L,R)$ 表示 $ma(L,R)$ 对应的 $b_i$，如果存在多个就取最右边的。
设 $\text{query}(L,R,p,q)$ 表示假如当前序列末尾对应 $a_i=p,b_i=q$ 时遍历区间 $(L,R)$ 得到的答案。
于是，如果 $a_i\gt ma(L,M)$，则 $\text{query}(L,R,p,q)=\text{query}(M+1,R,p,q)$。
否则，有 $\text{query}(L,R,p,q)=\text{query}(L,M,p,q)+\text{query}(M+1,R,ma(L,M),mb(L,M))$。
建立线段树，每个区间维护 $\text{query}(M+1,R,ma(L,M),mb(L,M))$。
这样，对一个询问，如果该询问正好对应一个线段树区间，则查询复杂度 $O(\log n)$。
否则，将该询问拆分成 $O(\log n)$ 个线段树区间，串联查询计算答案，时间复杂度 $O(\log^2 n)$。
对与修改操作，修改完暴力询问更新 $\text{query}(M+1,R,ma(L,M),mb(L,M))$，由于这是线段树区间，所以复杂度为 $O(\log n)$。
所以修改的总复杂度也是 $O\left(\log^2 n\right)$。总时间复杂度 $O\left(n\log n+q\log^2 n\right)$。
ps. 比赛写了 $O(nq)$ 的假算法，居然过了。
J. xay loves Floyd
题意
给定一个有向图，初始时 $\text{dis}(u,u)=0,\text{dis}(u,v)=\infty(u\neq v)$。
接下来给定若干条边 $(u,v,w)$，使得 $\text{dis}(u,v)=w$。询问以下两个程序最终结果中满足 $\text{dis}(u,v)$ 相同的 $(u,v)$ 对数。
for k from 1 to n for i from 1 to n for j from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])
for i from 1 to n for j from 1 to n for k from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j])
题解
首先 $n$ 次单点源最短路算法 $O(nm\log m)$ 求出 $\text{dis}$ 的真实值。
设 $ok(u,v)$ 表示 $\text{dis}(u,v)$ 是否为正确值，考虑第二个程序得到的 $\text{dis}(i,j)$ 正确的充要条件。
不难发现，只要 $i\to j$ 的最短路上有一点 $k$ 满足 $ok(i,k)\And ok(k,j)$ 即可。
首先考虑找到所有满足条件的 $k$，设 $\text{path}(u,v)$ 表示 $u\to v$ 上最短路的点集，于是有状态转移方程
$$ \text{path}(i,j)=\bigcup_{\text{dis}(i,k)+w(k,j)=\text{dis}(i,j)}\text{path}(i,k) $$
对固定的 $i$，考虑将 $j$ 按 $\text{dis}(i,j)$ 从小到大排序后用 $\text{bitset}$ 加速上述转移。
然后按 $1\sim n$ 顺序枚举 $j$，于是有 $\text{ok}(i,j)=\sum_{k=1}^n ok(i,k)\And ok(k,j)\And (k\in \text{path}(i,j))$。
用两种 $\text{bitset}$ 维护 $\text{ok}(i,\ast),\text{ok}(\ast,i)$，上述转移也可以用 $\text{bitset}$ 加速。总时间复杂度 $O\left(nm\log m+\frac {n^2m}w\right)$。
K. xay loves sequence
题意
给定一个长度为 $n$ 的序列 $A$，接下来若干询问，每次输出 $f(l,r,k)$。
定义 $f(l,r,k)$ 表示将 $A$ 的子串 $a[l\sim r]$ 全部变为 $0$ 的最小操作次数。
其中每次操作为选择 $a[l\sim r]$ 的一个子串 $a[l_2\sim r_2]$，令 $a_i\equiv a_i+1\bmod k(l_2\le i\le r_2)$ 或者 $a_i\equiv a_i-1\bmod k(l_2\le i\le r_2)$。
保证对所有 $k$ 满足 $k\gt a_i$。
题解
对每次询问的 $a[l\sim r]$，令 $a_{l-1}=0,a_{r+1}=0$，设 $b_i=a_i-a_{i-1}(l\le i\le r+1)$。
于是每次操作等价于选取一对 $l\le i,j\le r+1$，$b_i\equiv b_i+1\bmod k,b_j\equiv b_j+1\bmod k$。
同时，$\sum_{i=l}^{r+1} b_i=a_{r+1}-a_{l-1}=0$，最终目标是将 $b_i$ 全部变为 $0$。在不考虑取模的情况下，最小费用显然为 $\cfrac {\sum_{i=l}^{r+1}|b_i|}2$。
考虑取模，则最终有 $b_i=0,\pm k$，且仍然有 $\sum_{i=l}^{r+1} b_i=0$。
考虑将一些 $b_i\gt 0$ 的数目标设为 $k$，则对操作数的影响为 $\cfrac {k-2b_i}{2}$。将一些 $b_i\le 0$ 的数目标设为 $-k$，则对操作数的影响为 $\cfrac {k+2b_i}{2}$。
由于要保证 $\sum_{i=l}^{r+1} b_i=0$，所以可以设最终有 $x$ 个 $b_i=k$，同时有 $x$ 个 $b_i=-k$。
分别在 $b_i\gt 0$ 和 $b_i\le 0$ 的两个组数中取原来绝对值前 $x$ 大的 $b_i$ 显然是最优的。另外随 $x$ 增大收益显然具有单峰性。
于是二分答案即可。另外对于区间询问可以用主席树维护 $b[l+1\sim r]$ 的值，然后补充 $a_l,-a_r$。
时间复杂度 $O(n\log n\log v)$，空间复杂度 $O(n\log v)$。
