CF1827B2 Range Sorting (Hard Version)（单调栈/链表）
I_am_Accepted
·
·
题解
子串中一个 gap 有 1 的贡献当且仅当子串中 gap 之前的值 \max> 子串中 gap 之后的值 \min。
然后枚举子串 gap 之前的最大值位置，狂暴推式子，发现只要求得
-
每个位置 i 左侧第一个大于其的位置 L_i（没有 L_i=0）。
-
每个位置 i 右侧第一个大于其的位置 R_i（没有 R_i=n+1）。
-
每个位置 i 的 [R_i,n] 中最左侧的位置 X_i 使得 a_{X_i}<a_i。
答案就可以线性算了。
按 $a_i$ 从大往小删位置，维护剩下位置形成的双向链表，扫到值 $a_i$ 时查询一下位置 $R_i-1$ 在链表中的后继即可。
值离散化后复杂度线性。
[代码](https://codeforces.com/contest/1827/submission/206855325)
当然有严格线性的做法。
考虑每个位置 $i$ 的询问挂在节点 $R_i$ 上。倒序扫下标，维护如下图的单调栈。
在单调栈插入位置 $i$ 之前处理所有挂在 $i$ 点的询问下标集合 $S$。
从小到大遍历所有 $S$ 内的元素，设当前为 $j$。将目前单调栈中值 $>a_j$ 的栈顶依次弹出（这些位置必然不再会作为别人的 $X_i$ 了），然后将 $X_j$ 设为栈顶。
复杂度线性。
[代码](https://codeforces.com/contest/1827/submission/206894850)