题解：CF2147F Exchange Queries

令 $a_{p_i}=s_i$，这样 $(p_i,s_i)$ 变成了 $(x,a_x)$（也可以看成是以 $p$ 为关键字排序），显然此时后面的点能到前面的点。

考虑什么时候前面的点不能到后面的点，也就是 $[1,i]$ 内的点无法连向 $[i+1,n]$，也就是 $[1,i]$ 的值域为 $[1,i]$，这是充要的。称这样的 $i$ 是关键的。假设关键点为 $b_1,\cdots,b_k$，答案为 $\sum (b_i-b_{i-1})(n-b_{i-1})$，由于 $b_k=n$，这实际上可以化简为 $\sum b_i^2-\sum b_ib_{i+1}$。

考虑怎么维护这个东西，发现如果令 $c_i=\sum_{j=1}^ia_j-j$，注意到 $c_i\ge 0$，而有且仅有 $c_i=0$ 的 $i$ 是关键的。所以相当于是要支持区间加，维护区间最小值的一些信息，线段树维护即可，$O(q\log n+n)$。

code。