\(3500\)。
根本想不到这种思路。
先考虑这么一个问题：
给定 \(n\) 个区间 \([a_i,b_i)\)。
\(q\) 次询问，每次查询 \((\cup_{l\le i\le r}[a_i,b_i))\cap\mathbb Z\) 的元素个数。
允许离线。
考虑离线，在 \([1,n]\) 上右移一下标指针 \(r\)，每次把数轴上编号在 \([a_r,b_r)\) 内的元素均染为颜色 \(r\)。
则，容易发现，一次对 \([l,r]\) 的查询的答案此时就是全局颜色编号 \(\ge l\) 的元素个数。
于是就可以用一颗 ODT 动态维护全局各节点的颜色，用一颗线段树 / 树状数组维护当前各颜色有多少元素。当维护到 \(r\) 的信息时，计算其对应的 \([l,r]\) 询问答案。
这样，由颜色段均摊，此部分复杂度为 \(O(n\log n+q\log n)\) 的。
使用主席树，这个做法就可以支持在线查询了。
我们部分设对此询问的答案为 \(c(l,r)\)。
回到本题。
考虑先二分答案找出第 \(k\) 大值。
考虑怎么做。
现在，要 check：有多少段 \(c(l,r)\ge v\)。
考虑对每个右端点 \(r\) 计算答案。
容易发现，\(c(l-1,r)\ge c(l,r)\le c(l,r+1)\)，也即满足区间包含单调性。
因此，对于每个 \(r\)，其对应的合法 \(l\) 使得 \(c(l,r)\ge v\) 必然是一段连续的区间。
使用双指针即可找到合适的左端点 \(l\)。
使用简单技巧即可优化到每轮 \(O(n)\)；即，一次扫描预先记录各部分变化量，每次询问直接按照莫队的方式转移，因为只有单点修改查询所以不影响。
经过 \(O(\log v)\) 轮，即可找到对应的适合 \(v\)。
那么，再单次查询找到 \(<v\) 对应的答案之和以及数目，这个可以用线段树 / 树状数组区间加区间求和维护一下。
然后再补上 \(v\) 的贡献即可的解。
总复杂度 \(O(n\log n+n\log v)\)。
原文地址：http://www.cnblogs.com/myee/p/Luogu-solution-cf1034d.html
