CF1824D

fox-konata / 2023-08-25 / 原文

原题

翻译

我们定义\(f(l,r,x)=\sum_{j=1}^{x}{\sum_{i=l}^{\min{(j,r)}}{g(i,j)}}\)，容易发现对于一个询问的答案\(ans = f(l,r,y)-f(l,r,x-1)\)

我们扫描先维护右端点\(r\)从左向右移动，线段树下标\(i\)上的值维护的是\(g(i,r)\)

我们考虑再维护一个01数组\(b_i\)，表示\(a_i\)这个数是否是在\([i,r]\)中第一次出现。每次移动右端点时把当前位置戳成\(1\)，把上一个和该元素相同的位置戳成\(0\)。

我们发现\(g(i,r)\)就等于\(i\)之后第一个\(b_i=1\)的下标，于是我们找到\(r\)左边(不包括，因为我们已经修改\(b_r=1\))第一个\(b_i=1\)的位置，记作\(x\)，这个过程可以把\(b_i=1\)的位置放到\(set\)中维护，则对答案的影响是线段树区间\([x+1,r]\)赋值为\(r\)

而我们要找的答案即为右端点\(r=1 \rightarrow x\)的过程中所有区间\([l,r]\)的和

但这只是一个询问的情况，我们发现如果有\(Q\)个询问这么做显然是\(O(Qn\log n)\)的，是无法通过的

但我们发现我们实际上维护了这\(Q\)次询问的答案，只是我们要考虑如何快速的把他们累加

看一眼线段树3，我们发现这个“历史和”很符合我们的要求

于是我们只需要把所有询问离线，把\(x,y\)拆成\(\{l,r,x-1\}\)和\(\{l,r,y\}\)，线段树维护以下操作：