CF1034D
似乎是过的第一个 \(\color{red}3500\)?
注意题目要求的是并集，不是交集（看错题了，然后以为很水，其实自己很水。）
首先对于 \(r\) 来说，\(l\) 越小，区间的长度越大。
对于求前 \(k\) 大之和的题目，一般有两个方向（可跳过）。
-
当 \(k\) 较小，且具备一定单调性时（比如这题，\(r\) 固定，价值随 \(l\) 增大而减小*），可以使用优先队列。比如这个：[NOI2010] 超级钢琴
-
还有一种是二分先求出第 \(k\) 小 \(val\)，转化为计算所有价值 \(\ge val\) 的那些对的数量与价值之和。比如这个：CF241B
个人认为第二种适用范围广些，但也需依情况而论。
这个题因为 \(k\) 有 \(10^9\)，只能考虑第二种。
二分答案 \(val\)，如何计算数量呢？
首先从小到大枚举 \(r\)，先解决如何快速计算一个区间的价值这个问题。
最开始的想法是是对于一个区间 \([a_i, b_i]\)，相当于给这个区间内的数 \(+1\)，然后查询 \(0\) 的个数。这个在计算数量时尚且可行，但在计算价值和时就有些不会了。
换一个角度，考虑每个数的贡献，设 \(lst_i\) 表示 \(i\) 最后一次出现的位置，那么对于 \(l \le lst_i\) 有 \(1\) 的贡献。
从小到大移动 \(r\) 的时候，就是将 \([a_r, b_r]\) 内的数修改为 \(r\)，可以用 ODT 维护，进而得到对于一些一些 \((p_i, q_i, v_i)\)，表示对于 \(l \in [p_i, q_i]\) 新产生 \(v_i\) 的贡献，使用树状数组即可。这样计算价值和也是比较舒服的。
设 \(lmax_r\) 表示对于 \(r\) 时，最大的 \(l\) 使得 \([l, r]\) 价值 \(\ge val\)。和 * 一样，\(lmax_r\) 单调递增。并且可行的 \(l\) 本身就是一段前缀，就可以使用双指针求 \(lmax_i\)。
于是就做到了 \(O(n \log n \log V)\)，应该过不了。
考虑继续优化，首先二分的 \(\log\) 少不了，只能优化掉另一个 \(\log\)。
首先关于 set，不难发现 \((p_i, q_i, v_i)\) 是跟 \(val\) 没关系的，就可以搬到外面。
而关于树状数组，也可优化。相当于解决区间加，单点差的问题。一般情况下确实只能树状数组，但这个题的特殊之处在于查询是单调不减的（\(lmax\)），这就可以直接差分（维护差分数组 \(d\)）。
for (auto &[l, v] : tagd[i]) { // (p[i], q[i], v[i]) = (l, i, v)，因为 q[i] 就是 r d[l] += v, d[i + 1] -= v;if (l <= j) s += v, ss += (j - l + 0ll) * v; // ss 是用来维护价值和的。
}
移动 \(lmax\) 指针时，这样就行：
for (; j <= i && s >= len; ) { // j 是 lmaxss += s, s += d[++j];
}
计算价值和时，可以最后在用线段树计算。当然也就可以 check 时计算，ss 就是对于 \(r\) 的所有 \([l, r]\) 的价值和。
时间复杂度：\(O(n \log V)\)，主要 set 常数大。