yaohaoyou

$\Large\color{red}\Diamond$ 是关键转化。

pingpong

赛时。

多次询问是假的，直接离线排序。首先 $\sum freq\le 10^6$ 是好做的，只要花费 $\mathcal O(\log n)$ 的时间消掉一个网即可。正解考虑优化这个过程，首先会处理左右端点有多个相同位置的网的情况，直接可以 $\mathcal O(1)$ 消掉一个位置所有的网，然后每次就可以花费 $\mathcal O(\log n)$ 让 $T\gets T-dis,dis\gets dis+1$，所以只会有 $\mathcal O(\sqrt T)$ 种坐标，将所有完全相同的网合并后，每种网只会出现 $\mathcal O(\frac{\sqrt{T}}{len_i})$ 次，所以总和为 $\mathcal O(\sqrt T\ln \sqrt T)$，复杂度是 $\mathcal O((N+\sqrt T)(\log N+\ln \sqrt T)+Q\log Q)$。

select

赛后。感觉 $\mathcal O(n^2)$ 和正解没有任何关系啊，不会分治还是太菜了。

首先是即使没有观察到性质也应该想到 $\mathcal O(n\log^2n)$ 的分治做法。分治后钦定第一个区间一定要过 $mid$，离线掉一维后就只要做对于 $b$ 数组的每种选择 $[l_2,r_2]$ 找到包含 $mid$ 的极长合法段 $\Large\color{red}\Diamond$。首先 $b_{l_2-1}$ 和 $b_{r_2+1}$ 显然只会是与当前分治区间 $a[l,r]$ 颜色相同的点或 $l_2=1/r_2=m$，否则扩展后一定更优，于是也可以将 $b$ 数组删到只剩 $r-l+1$ 个。

$[l_2,r_2]$ 是二维状态，考虑对 $r_2$ 扫描线，同时数据结构在 $l_2$ 维护 $[l_2,r_2]$ 的状态。对于 $b$ 选择 $[l_2,r_2]$，维护 $[L,R](L\le mid\le R)$ 表示 $a[L,R]$ 是与 $b[l_2,r_2]$ 不重的极大区间，显然对于同一个 $r_2$，随着 $l_2$ 增大对应的 $L$ 单调不增，$R$ 单调不减，所以可以使用类似单调栈的思路解决。当 $r_2\gets r_2+1$，令 $b_{r_2}=a_x$，若 $x\le mid$，所有的 $L$ 和 $x$ 取 $\max$。若 $x\ge mid$，所有的 $R$ 和 $x$ 取 $\min$，刚好对应一段后缀，单调栈维护即可，过程中需要做区间加求区间最值，总复杂度 $\mathcal O(n\log^2 n)$。

考虑用性质优化，首先显然答案至少为 $\max(\sum x,\sum y)$，而最后的答案为 $x[l_1,r_1]+y[l_2,r_2]$，所以一定有 $x[l_1,r_1]>\frac{\sum x}2$ 或 $y[l_2,r_2]>\frac{\sum_x}2$，否则还不如全选一个区间，所以找到最小的 $\sum_{i=1}^px_i\ge\frac{\sum x} 2$，$\sum_{i=1}^q y_q\ge\frac{\sum y}2$，则一定有 $[l_1,r_1]$ 跨过 $p$ 或 $[l_2,r_2]$ 跨过 $q$，然后就不用分治和去重了，把 $p,q$ 当作上面的 $mid$ 做即可，复杂度为 $\mathcal O(n\log n)$。

区间

赛后。这个也太抽象了，第一步都想不到。

首先有个显然的性质，一次取肯定会取完一个 LDS，所以可以考虑直接将 LDS 缩起来。（这个是赛时想到的）

然后就是将这个思路继续拓展。实际上，由于一个LDS内的选取顺序一定是连续的，所以影响他们什么时候取的就只有平均数（总和）了 $\Large\color{red}\Diamond$，所以对于相邻同侧的两个块 $(s_1,len_1)$，$(s2,len_2)$ 只要满足 $\frac{s_1}{len_1}\ge \frac{s_2}{len_2}$ 就一定会取完第一个块后立刻取第二个块（因为平均值拼上会更大），所以直接将两个块合并。此刻，$k$ 左右两侧的块就会分别单调了，即平均值形成 \k/ 的样子，对于先选左边和先选右边做差后能证明先选平均值更小的一定更优，所以直接将左右的块组成的序列归并就能得到操作顺序了。

现在需要一个数据结构，支持增删区间，维护排序后的带系数的全局贡献和，直接使用平衡树维护，插入删除对其他贡献系数的影响求区间和即可。也可以提前将所有的单调栈的块信息预处理后按平均值离散化后在线段树上做单点修区间求和，复杂度 $\mathcal O(n\log n)$。

序列

赛后。其中 $\mathcal O(n\sqrt n\alpha(n))$ 和 $\mathcal O(n\log n)$ 的做法都在代码源的题解中亦有记载，不改题导致的。

首先 $\mathcal O(n\sqrt n \log n)$ 的做法很显然，如果使用莫队尝试根号平衡。这个应该是比较套路的做法了，使用回滚莫队后，如果右端点只有向右移动，则每次就类似于初始时 $b_i=-i$，给后缀加一，求最后一个 $\ge 0$ 的位置。考虑使用单调栈维护后缀最大值，每次增加 $[x,n]$ 就找到 $x$ 在单调栈中的前驱后继（包括 $x$），然后将前驱删除，这个过程不难用链表+并查集维护。然后考虑左端点也可能会乱动，如果暴力撤销单调栈和链表会影响复杂度均摊，所以考虑和询问平衡复杂度。

考虑对值域分块，维护每个块内的后缀最大值（单调栈），后缀加 $[x,n]$ 的时候会将 $x$ 所在块分裂，只要使用上面的链表+并查集维护单调栈即可，然后剩余的块直接在 $id_x+1$ 打上差分标记即可，询问时再做前缀和。比较妙的是可以提前将 $a_l$ 的 $\sqrt n$ 种取值也作为分块的端点，这样所有的后缀加/减都只要打差分标记了，不会因为维护单调栈而影响均摊。查询的时候先找到答案在那个块后在块中跑单调栈即可，总复杂度为 $\mathcal O(n\sqrt n\alpha(n))$。

另一种做法就是让 $x$ 从 $n$ 到 $1$，由于对于 $[l_1,r_1]\sube [l_2,r_2],ans[l_1,r_1]\le ans[l_2,r_2]$，所以可以在求出 $ans[l_2,r_2]$ 前忽略 $[l_1,r_1]$，这样当前的询问区间就是互不相交的，所以左右端点分别递增，可以使用线段树维护后缀加，当确定一个 $ans[l,r]=x$ 时，将 $[l,r]$ 删除，然后在线段树上二分来加入新的极长询问区间。复杂度 $\mathcal O(n\log n)$。