2023 ICPC Seoul Regional Apricot Seeds 题解

题意

给你一个长度为 $n$ 的序列，有 $m$ 次询问，每次有五个参数 $[l~r~k~x~y]$ 。

表示区间 $[l,r]$ 单独拿出来，做 $k$ 次冒泡排序后，区间 $[x,y]$ 的和。

做法

$pjudge$ 提供的做法是枚举一个阈值然后转成 0/1 序列，个人觉得不好理解。

我们模拟两组数据：

2 7 9 8 5 3 4 1 6 1 | 
  2 7 8 5 3 4 1 6 1 | 9
    2 7 5 3 4 1 6 1 | 8 9
      2 5 3 4 1 6 1 | 7 8 9
        2 3 4 1 5 1 | 6 7 8 9
          2 3 1 4 1 | 5 6 7 8 9
            2 1 3 1 | 4 5 6 7 8 9
              1 2 1 | 3 4 5 6 7 8 9
                1 1 | 2 3 4 5 6 7 8 9
                  1 | 1 2 3 4 5 6 7 8 9

--------------------------------------------

2 9 3 6 1 8 2 7 |
  2 3 6 1 8 2 7 | 9
    2 3 1 6 2 7 | 8 9
      2 1 3 2 6 | 7 8 9
        1 2 2 3 | 6 7 8 9
          1 2 2 | 3 6 7 8 9
            1 2 | 2 3 6 7 8 9
              1 | 2 2 3 6 7 8 9

发现了 $x_{k+1}~x_1~x_2~\dots~x_k~~(x_1, x_2, \dots , x_k \leq x_{k+1}$ )

会变成 $x_1~x_2~\dots~x_k~x_{k+1}$ 。

这启示我们可以尝试从前缀寻找关系（对于询问的区间 $[x,y]$ ，可以视为 $[1,y]-[1,x-1]$ ）。

对于一次操作，我们尝试考虑前缀 $[1,i]$ 进行一次 冒泡操作 的变成的串。

Hint 1

如果一段进行了冒泡的极长子串 $x_{k+1}~x_1~x_2~\dots~x_k$ 所对应的 $a_j~a_{j+1}~\dots~a_{j+k}$ 满足 $j+k\leq i$ ，那么这段前缀的 $sum$ 不会被影响。

证明：所有冒泡影响的操作均在 $[1,i]$ 中进行，当然没有影响。

Hint 2

如果一段进行了冒泡的极长子串 $x_{k+1}~x_1~x_2~\dots~x_k$ 所对应的 $a_j~a_{j+1}~\dots~a_{j+k}$ 满足 $j+k> i$ ，那么这段前缀的 $sum$ 会变成区间 $[1,i+1]$ 的前 $i$ 小的值的和。

证明：我们对 $j+k=i+1$ 与 $j+k>i+1$ 分别进行证明。

首先经过一次冒泡排序后前缀 $[1,i]$ 会变为 $a_1 ~ a_2 ~ \dots ~ a_{j+1} ~ a_{j+2} ~ \dots ~ a_{j+k} ~ a_{j}$

（注意此时的 $a_k$ 表示的是值，不是下标为 $k$ 的元素。此时的定义与下面不同）。

因为 $a_{j+k}<a_j$ （注意此时的 $a_k$ 表示的是下标为 $k$ 的元素，不是值），所以前缀 $[1,i]$ 的 $sum$ 是区间 $[1,i+1]$ 的前 $i$ 小的值的和。

此时有 $max\{ a_1,a_2,\dots,a_{j+k} \} > a_{i+1}$ , $a_{j}=max\{ a_1,a_2,\dots,a_{j+k} \}$ 。

反证即可，如下：

若 $max\{ a_1,a_2,\dots,a_{j+k} \} \leq a_{i+1}$ ，则与 $j+k>i$ 矛盾，故 $max\{ a_1,a_2,\dots,a_{j+k} \} > a_{i+1}$ 。
若 $a_{j}\not =max\{ a_1,a_2,\dots,a_{j+k} \}$ ，则值为 $max\{ a_1,a_2,\dots,a_{j+k} \}$ 的，在区间 $[1,i]$ 最右边的一个元素会一直冒泡移动至 $i+1$ 。
与此时 $x_{k+1}~x_1~x_2~\dots~x_k$ 是极长子串矛盾。

综上，前缀 $[1,i]$ 的 $sum$ 会变成区间 $[1,i+1]$ 的前 $i$ 小的值的和。

我们尝试把 Hint 2 推广至 $l$ (注意字母) 次冒泡排序后的结果。

结论：前缀 $[1,i]$ 的 $sum$ 在经历 $l$ 次冒泡操作后，会变成 $[1,i+l]$ 的前 $i$ 小的值的和。

考虑对前缀 $[i,1]$ 进行归纳。

当 $l=1$ 时，上所述以证明。
当 $l=l'+1$ 时，我们对于一段进行了冒泡的极长子串 $x_{k+1}~x_1~x_2~\dots~x_k$ 分类讨论：

为了方便，设 $x_{k+1}~x_1~x_2~\dots~x_k$ 在原序列中对应 $a_j~a_{j+1}~\dots~a_{j+k}$ (不保证 $j+k\leq i$ ) 。
- 当 $j+k\leq i$ 时，所有操作均在前缀 $[1,i]$ 内进行，对区间 $[1,i]$ 的 $sum$ 不会产生影响。
  
  特殊的，当 $j+k=i$ 时，因为这段子串是极长的，所以有 $a_{j+k}\leq a_{i+1}$ ，仍不会对前缀 $[1,i]$ 的 $sum$ 不会产生影响。
- 否则有 $j+k>i$ 。此时会把 $max\{ a_1,a_2,\dots,a_{j+k+l-1} \}$ 从前缀 $[1,i]$ 的 $sum$ 中减去，并加入 $a_{j+k+l}$ 。
此时前缀 $[1,i]$ 的 $sum$ 变为前缀 $[1,i+l]$ 的前 $i$ 小的值的和。