题解-AGC012

反着做，对于每个点 (x), 记录 (f(x)) 表示最大的 (d) 使得对 (x) 进行了一个长度为 (d) 的操作。

然后对于一个操作把和 (x) 距离不超过 (k) 的点染色，拆分成把他旁边所有距离不超过 (k - 1) 的点染色。

如果 (k le f(x)) ，那么不执行操作。

时间复杂度 (Theta(nd))

在左边放 (1...100)，答案是右边的上升子序列个数。

假设空序列也算进答案。考虑从小往大放，放左边子序列个数增加 (1)，右边子序列个数乘 (2)。

二进制拆分即可。时间复杂度 (Theta(log n))

考虑两个同色的点都可以和同色最小值交换，那么他们俩可以交换。如果一个点可以和同色的最小值交换，那么把这个点的值视为这个同色最小值。

然后考虑不同色的点，那么如果一个点和其他不同色的点交换 (只需要判其他点的 (min)) ，那么他也能和 能和不同色点交换的点 交换，于是这些点都可以互相交换，组合数学算一下答案即可。

时间复杂度 (Theta(n))

对于第 (i) 个问题，可以转化为把整个序列拆分成 (1 + log v) 个序列（拆分后可以重新排列序列顺序），使得第 (1) 个序列包含了 (i)，且第 (i) 个序列的相邻两点的差 (le frac{v}{2^{i-1}})

记录 (fl_{i, j}) 表示第 (j) 个序列使用在 (i) 身上能到达的最小左端点，让 (fr_{i, j}) 则为最大右端点。

考虑记录 (pre_{mask}) 表示使用了 (mask) 中所有二进制位为 (1) 的位置已经被使用了的能到达的最大前缀位置，记录 (suf_{mask}) 为能到达的最大后缀位置。

答案就如果对于一个位置 (i) 满足 (pre_{mask} ge fl_{i, 1} - 1) 且 (suf_{mask oplus MAXN} le fr_{i, 1} + 1)，那么就是可行的。

但是这样是 (O(nv)) 的，不能通过。

考虑用第 (1) 个序列来把序列分段 (如果相邻两个距离 (> v) 就断开)，如果段数 (> log v + 1)，那么一定不可行。

所以对于每一段判断一下答案可不可行即可。

时间复杂度 (Theta((v + n) log v))

待填坑