题解：CF2147F Exchange Queries

diqiuyi · 2025-09-23 21:11:43 · 题解

令 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。