单轮操作只需要维护两个指针 p,q，初始 p=0,q=n+1，每轮 p 向后扫过 x 个 1，q 向前扫过 y 个 0，若 p\gt q 则停止并返回当前轮数。考虑将这个过程形式化，设 A_i 表示 i 及之前 1 的个数，B_i 表示 i 及之后 0 的个数，则所求即 \max_{i=0}^n\min(\lceil \frac {A_i}x\rceil,\lceil \frac{B_{i+1}}y\rceil)，含义即为每对 i\lt j,b_i=1,b_j=0 的 (i,j) 均需要交换前后顺序，对它们需要的轮数取最大值。
此时从小到大枚举 p，每次只会将一个 1 变成 0，这会对 A 的一段后缀以及 B 的一段前缀进行修改，两个树状数组即可维护。同时由于 A 不降且 B 不增，找到 \lceil \frac {A_i}x\rceil\le\lceil \frac{B_{i+1}}y\rceil 的最后一个位置 t 后，只需要对 i=t 和 i=t+1 取最大值即可。而修改是减少 A 且增加 B，因此 t 的位置也是不降的，每次更新后尝试向后移动 t 即可，时间复杂度 O(n\log n)，提交记录。
事实上，对于每个分界点 p 来说，目标是令其前面全为 0，后面全为 1，因此在 x=y 时（比如原题的 x=y=1），每次就会将 p 前面的 x 个 1 扔到后面，之后将 y=x 个 0 扔回来，答案就是 \lceil \frac {\max_{p} \sum_{i=1}^p [a_i>p]} x\rceil。然而 x\ne y 时进出不相等，比如 y< x 时扔到后面 x 个 1，然而递补过来的 (x-y) 个值不确定，因此不能这么做。
09.24 思考题 区间排序
我说这才是排序分析。
有一个长为 n 的序列 a，给出操作 s(l,r)，表示对序列 a 该区间升序排序，称一个排序过程合法当且仅当所有可能的序列 a 在经过这些操作后均不降。
是可以的，仍然考虑 01 串，定义 p 不劣于 q 当且仅当两者长度相同，1 的个数相同，且对于每个相同排名的 1，在 p 里的位置均不比在 q 里靠前。这个定义下并非任意两串都能分出优劣（比如 0110 和 1001），但这是具有传递性的，且升序合法状态比其他串都不劣，降序串比其他串都劣。
更进一步地，每个串每次操作都不会变劣，且若 p 不劣于 q，两者均经过某操作 s(l,r) 后得到的 p',q' 一定满足 p' 不劣于 q'，证明只需要考虑两者该区间内 1 的变化即可。由此无论操作序列如何，降序串一直是最劣的，因此降序串合法就能说明原串合法。再结合第一条即可说明该结论。
哪些常见排序算法可以描述成上述区间排序过程？
冒泡排序，且满足 r-l+1\le 2。
插入排序，方式是依次进行 i\in[1,n] 的所有 l=1,r=i。
归并排序，先递归到 [l,mid],[mid+1,r]，再进行 s(l,r) 的归并过程。
[AGC001F] Wide Swap
题意
给出长为 n 的排列 p，可进行任意次交换 p_i,p_j 的操作，但必须满足 \left|i-j\right|\ge k 且 \left| p_i-p_j\right|=1，求字典序最小的最终排列。n\le 5\times 10^5。
题解
有值限制的任意交换太困难了，考虑转化为逆排列 q_{p_i}=i，并在 q 上进行交换。这时限制变为 \left|q_i-q_j\right|\ge k 且 \left| i-j\right|=1，第二个限制就是相邻了，这样看起来就好了很多。同时字典序最小的 p 对应的是倒序字典序最大的 q，证明考虑首先要让 q_x=1 的 x 尽可能小，也就是从小到大依次尽可能靠前，那么从后往前依次填尽可能大的数就是对的。
由于只能邻项交换，考虑初始序列 q 和最终序列 r，若 q 中 x 在 y 前面，r 中 x 在 y 后面，则交换过程中一定直接交换过 x,y 两个值，因此要求 \left|x-y\right|\ge k。每一对值均有该限制，存在限制无法满足的最终序列一定操作不出来。
若能证明满足限制的最终序列 r 一定能操作出来，那么就可以这样刻画合法序列。考虑构造 q 变成 r 的操作，方式是依次将 q 的每一位变成与 r 相同，若目前不同则从后面依次交换过来，然后忽略第一位继续向后构造。若过程中出现无法交换的情况，此时这两个值的先后顺序一定需发生变化，这说明 r 无法满足该限制，而这是不可能发生的。因此一定能构造出 r。
将该限制重写回 p，则对于所有 \left|i-j\right|\lt k 的下标 i,j，若初始时 p_i<p_j，则最终也一定有 p_i\lt p_j，求字典序最小的 p。这是一些偏序限制，然而解决方式并非由 i 向 j 连边，再进行取最小值的拓扑；而是应该建反向边，并进行取最大值的拓扑，并依次为其赋上从大到小的值。比如 n=3 时只有 (3,1) 的限制就能卡掉。然而本题的边比较特殊，错误方式也能过。
这样我们得到了 O(n^2) 的拓扑排序做法，优化可以使用线段树隐式建图，考虑 i 的入度为零表现为只考虑未处理的点时，i 在 p 的 (i-k,i+k) 区间内为最大值。因此用线段树维护该过程，用堆维护目前入度为 0 的所有点，每次取出堆顶 i 时只需要查看 (i-k,i) 和 (i,i+k) 两区间内是否有点入度变为 0 即可。时间复杂度 O(n\log n)，提交记录。
另一种考虑方式是类似前置，直接找到倒序字典序最大的 q，最后再转回原排列。考虑直接任取一个 q_i-q_{i+1}\ge k 并将其交换，直到不存在这样的 i，并证明这样一定能操作到最优解。
因此只进行 q_i-q_{i+1}\ge k 的操作即可，同前置可用冒泡排序维护该过程，即每次从头到尾试图进行合法操作，从而确定 r_n 的值，再对前 n-1 个数进行操作。容易分析出这样放到结尾的一定是能到结尾的最大值，时间复杂度 O(n^2)。
优化考虑前置中区间排序状物的排序算法，其中只有归并排序是 O(n\log n) 的，因此尝试用归并排序代替冒泡排序，每次将左右两边归并起来，从后往前确定值。此时右边可以直接放，左边的 x 要放必须越过右边未放的所有元素。
该限制看似困难，然而只要右边还有比 x 大的数 y，此时就一定不会放 x，同上面的证明过程，x 跳过 y 后只有再跳过比 x 小的元素才能更优，然而这不可能存在，否则右边还能操作。综上 x 只在比剩余最大值 y 大时会被放，且需满足 x-k\ge y，预处理右边前缀最大值即可快速查询 y。总时间复杂度 O(n\log n)，常数比上种做法小得多，提交记录。
09.26 括号序列
其实不止是括号序列，一些类似匹配消除的序列也可以归入此类。
P9753 消消乐
参见【做题记录】P9753 + CF1223F，有补充，此处略过不表。
P7323 [WC2021] 括号路径
题意
给出一张 n 个点 2m 条边的有向图，输入的 m 组 (u,v,w) 同时表示 (u,v,w) 和 (v,u,-w) 两条边，正负分别表示该种的左右括号。求有多少组 x\lt y 满足存在一条边权为合法括号序列的从 x 到 y 的路径。n\le 3\times 10^5,m\le 6\times 10^5。
给出序列 a，求值域为 [1,m]，且所有子区间的最靠左最大值位置均与 a 相同的序列 b 数量。多组数据，取模，\sum nm\le 10^6。
题解
对序列建出大根笛卡尔树，子区间最靠左最大值位置即两端点 LCA，因此要求 b 序列的笛卡尔树结构与 a 相同。在 a 的笛卡尔树上进行树形 DP，设 f_{u,i} 表示 u 点值为 i 时子树内方案数，转移为 f_{u,i}=(\sum_{j=1}^{i-1}f_{lc_u,j})(\sum_{j=1}^i f_{rc_u,j})，用前缀和优化即可做到 O(nm)。
[ABC262Ex] Max Limited Sequence
题意
给出若干限制 l,r,x，表示要求 a 序列的 [l,r] 区间最大值为 x。求值域在 [0,m] 内的合法 a 序列数量。取模，n,q\le 2\times 10^5,m\lt mod=998244353。
题解
这是 LCA 所说没那么板的区间最值题。要求形如区间均不超过 x，且至少存在一个 a_i=x，此时每个位置都有一个最低下界 b_i，这可以随便用数据结构求出。之后再考虑区间存在 x 的限制。注意到区间 b_i\le x，不存在超过 x 的 b_i，因此只考虑 b_i=x 的位置即可。
所以将位置按 b_i，限制按 x 分类，对这些位置和限制一起算方案数，限制形如某些区间内至少有一个取到上界，不取到上界的 x 种值是等价的。这就容易 DP 了，可设 f_{i,j} 表示考虑完了前 i 个位置，目前左端点在 i 之前且仍未覆盖的右端点最大值为 j，转移形如前缀乘、后缀查和单点加，直接用线段树维护即可，时间复杂度 O((n+q)\log n)。