uwu
CF2147F Exchange Queries
不是人类能想出来的。
记 \(a_{s_i}=p_i\)，对于 \(i,j\)，若 \(i>j\) 或 \(a_i>a_j\)，就连一条有向边 \((i,j)\)，修改是交换，查询的是图中 \(i\) 能到 \(j\) 的个数。
你发现这个图是一个竞赛图加上若干条边，所以缩点后是一条链。
我咋知道咋注意到的，记所有满足 \(\max\limits_{j=1}^{i}a_j=i\) 的点从小到大排序后为 \(p_{1},\ldots,p_{k}\)，那么所有 scc 是 \((p_{i-1},p_i]\)，这里 \(p_0=0\)。
给一坨证明：
后面再写。
答案就是 \(\sum\limits_{i=1}^{k}p_i\times(p_i-p_{i-1})=\sum\limits_{i=1}^{k}p_i^2-\sum\limits_{i=1}^{k}p_i\times p_{i-1}\)。
记 \(b_i=i-\sum\limits_{j=1}^{i}[a_j\le i]\)，那么 \(\max\limits_{j=1}^{i}a_j=i\) 相当于 \(b_i=0\)。
如果知道 \(b\) 长啥样，答案就很好维护了，开个线段树，每个节点维护一下答案、最小值、最小值最左/最右的位置。
你注意到一个位置 \(i\) 只会对 \([\max(i,a_i),n]\) 内的 \(b\) 造成 \(-1\) 的贡献，就做完了。
