感觉我的数据结构太弱了?，所以有了这个恶补计划。
CF1824D
给定一个常为 \(n\) 的数列 \(a_{1,2\dots n}\)，定义 \(g(i,j)=\begin{cases}\max(x|\{a_k|i\leqslant k\leqslant j\}\subseteq\{a_k|x\leqslant k\leqslant j\})&,i\leqslant j\\0&,i>j\end{cases}\)。\(q\) 次询问，求 \(\sum\limits_{i=l}^r\sum\limits_{j=x}^yg(i,j)\)。
\(n,q\leqslant 10^6\)
考虑 \(g(i,j)\) 的意义，即“最小的与之颜色数相等的后缀的左端点”，发现这个东西和右端点关系紧密，考虑将所有 \(j\) 相同的 \(g(i,j)\) 统一处理。
我们记 \(b_{i,j}\) 表示 \(i\) 到 \(j\) 中最大的 \(k\)，满足 \(a_i=a_k\)。
则 \(g(i,j)=\min\limits_{k=i}^jb_{k,j}\)。考虑将 \(j\) 变为 \(j-1\)，则所有的和 \(a_j\) 颜色相同的点的 \(b\) 值会变化，具体的，记 \(pre_i\) 是最大的 \(x<i\) 满足 \(a_x=a_i\)，这些点的 \(b\) 值会变成 \(pre_i\)，将这个操作还原到 \(g\) 即为对于所有的 \(x\leqslant pre_i,g(x,j-1)=\min(g(x,j),pre_i)\)。
考虑将 \(j\) 这一维从大到小扫描线，我们就需要维护前缀 \(g_i\gets \min(g_i,x)\) 和前缀历史版本和。但是 \(g0_i\gets \min(g_i,x)\) 操作时众所周知的单次 \(O(q\log^2n)\)，所以考虑推敲一点性质。
发现用线段树维护的数列 \(g\) 是单调递增的，这意味着我们可以将区间取最小值操作变成区间推平操作。现在的难点就变为如何在维护区间推平操作的同时维护历史版本和。
我们对于每一个点的历史版本和，我们改写成 \(g_it+h_i\) 的形式，其中 \(t\) 为查询的时刻，对于没有修改的部分，可以直接查询；对于一个没有推平标记的节点，可以直接将其修改成 \(xt+h_i-(x-g_i)t'\) 即可，其中 \(t'\) 为推平时刻。
现在的问题在于如何合并两个标记，因为这个标记接下来还需要一起下传，就会导致有被额外计算的部分，具体如下图：
额外维护一个数组处理这个额外计算的部分即可。
时间复杂度 \(O(n+q\log n)\)，常数较大，但是可以通过。