模拟赛 11 题解 | AlanSP's Blog

数论+置换+数据结构+思维+dp+斜率优化

详见luogu裴蜀定理模板。

推广：对于 $n$ 元一次方程 $ax+by+cz+\dots=d$ ，有解的充要条件是 $\gcd(a,b,c,\dots)|d$ 。

证明可以移项，注意特判全为0的情况

对前缀和的理解++。

事实上，只要有结合律，存在逆变换的操作就可以进行前缀和和差分。

不难发现置换和逆置换是可以抵消的，也就是我们可以构造出一个 "置换" 的前缀和，存的是变换后的数组。

同时我们构造一个逆置换的前缀和，用来差分。

其中逆置换 $rev$ 表示按照这个数组的下标输出，能得到抵消这几次操作的数组。

构造方式考虑权值和下标的对应关系， $rev[j]=map[j]$ ，即权值为 $j$ 的对应下标。

挺好的题。

有序的情况下，当且仅当 $s_i+1<a_{i+1}$ 的时候，出现最小不能被表示的数，即 $s_i+1$ 。

这个很好理解，考虑归纳法，我们已经能凑出 $[1,s_i]$ 的所有数。

如果 $a_{i+1}\leqslant s_i+1$ ，我们可以先用之前的数凑出 $s_i-a_{i+1}+1$ ，这样就能凑出 $a_{i+1}+1$ 。

现在问题转化为了如何找到这个 $s_i+1$ 。

我们考虑每次迭代，找到 $\leqslant s_i+1$ 的数，把它扔到前缀和里面去，不断扩大 $sum$ 的范围。

这样一直做，知道找不到为止，这样的复杂度是 $O(n\log n)$ 的。~~我不会证~~

所以瓶颈在于如何快速找到区间内小于等于某个数的个数。

这个可以用主席树或者离线树状数组轻松维护，总复杂度 $O(n\log^2n)$ 。

首先有一个暴力dp：

f[i][j]=\max_{x\le i \& y\le j}(f[x][y]+(i-x+j-y)\times b[x][y])+a[i][j]

其中 $f[i][j]$ 为强制拿 $(i,j)$ 的 $val$ 的最大权值和。

考虑优化，先推一下式子：

f[i][j]-a[i][j]=(i+j)\times b[x][y]+f[x][y]-(x+y)\times b[x][y]

我们把 $(i+j)$ 看成 $x$ ， $b[x][y]$ 看成 $k$ ， $f[x][y]-(x+y)\times b[x][y]$ 看成 $b$ ，这就是一条直线的形式。

我们现在要找到一个 $(x,y)$ ，满足在 $i$ 下直线的高度最大。

维护一些直线，我们可以采用李超线段树。

注意，此题还要满足一种偏序关系 $x\le i\and y\le j$ ，由于是二维偏序，在外面套个树状数组即可。