比赛链接

Solved by Potassium.

给一个长度为 $n$ 的排列，每次将一段区间升序或降序排列，求最后中间位置的数。

显然可以对答案进行二分。设当前二分的数为 $x$ ，令 $b[i]=(a[i]\ge x)$，模拟每次操作即是区间置 $0$、区间置 $1$ 和区间求和，线段树维护一下即可。

Solved by .

Solved by .

Solved by .

Solved by .

Solved by .

Solved by .

Solved by Potassium & nikkukun.

给一个长度为 $n$ 的 $01$ 序列，一次操作是将某个元素取出并插入到任意位置。$q$ 次询问 $k_i$ 次操作后最长的连续 $0$ 长度。

对 $1$ 的操作相当于删掉 $1$ 也即合并两段连续 $0$，对 $0$ 的操作相当于向最长连续 $0$ 段添加 $0$。

考虑求出答案区间 $[l,r]$ 。设 $0,1$ 的前缀和分别为 $s_0,s_1$，则区间满足 $s_{0,r}-s_{0,l-1}\le k$ 条件，且 $(s_{0,r}-s_{0,l-1})+(k-(s_{1,r}-s_{1,l-1}))$ 最大。式子化为求 $(s_{0,r}-s_{1,r})-(s_{0,l-1}-s_{1,l-1})$ 最大的合法区间。设 $f_i=s_{0,i}-s_{1,i}$ ，维护一个递增的单调队列即可求出答案。