求 \(\sum\limits _ {i = l} ^ r \sum\limits _ {j = x} ^ y g(i,j)\)。
离线询问,扫描线 \(j\),线段树维护 \(g(i)\),那么,转换为求解 \(x\) 时刻到 \(y\) 时刻,线段树区间 \([l,r]\) 的区间和的历史和。
考虑扫描线 \(j \leftarrow j + 1\) 时,会如何变化。
我们设一个辅助数组 \(s_i\) 表示一个位置是否是这个值的最后一次出现。那么 \(g(i)\) 相当于说 \(\ge i\) 中 \(s = 1\) 的最小下标。
而我们 \(j\) 移动时,\(s_{pre_j}\leftarrow 0, s_j \leftarrow 1\)。
然后,我们就要在 \(g\) 的这个线段树上对本身 \(pre_{a_j}\) 到上一个 \(1\) 的位置中这些值都变成 \(pre_{a_j}\) 的后一个 \(1\),并且把 \(j\) 的位置修改成 \(j\)。
其中 \(pre_i\) 表示满足 \(a_j = i\) 的最大的 \(j\)。
线段树要支持:区间推平,区间查询历史和。
维护一个向量 \(\begin {bmatrix} hsum, sum, len\end{bmatrix}\)。
修改矩阵:
\[\begin{bmatrix}1 & 0 & 0\\0 & 0 & 0\\0 & v & 1\\\end{bmatrix}
\]
更新历史和矩阵:
\[\begin{bmatrix}1 & 0 & 0\\1 & 1 & 0\\0 & 0 & 1\end{bmatrix}
\]
我们需要查询当前某个数前面/后面第一个 \(s=1\) 的位置,那么我们需要维护下标集合,用一个 std::set
即可。