很久之前的研究成果了。不过现在还是说一下。

简单来讲，这个问题应该可以在同样的复杂度内对询问在线，至少可以在两个 log 的复杂度内对询问在线并做到更强的询问形式，并且完全没有利用答案的包含单调性（不过答案的包含单调性确实很重要）

请原谅笔者的精力有限。可阅读 incent 或 atgc 对本题的提交

26.3.15

问题内容

对于多重集合 $A$，定义其 间断点 为满足 $\#(A\cap[0,p-1])=p-1$ 的所有点 $p$。

记号 $\#(A\cap[0,p-1])$ 表示 $A$ 中 $\le p-1$ 的元素个数。

给定序列 $a$，多次查询，每次给定下标的区间 $[l,r]$，查询 $a[l,r]$ 的最大间断点。

考虑如下算法：

对于一个多重集 $B$，定义关于 $k$ 的 容量函数 $F_k(B)=\#(B\cap[0,k])-k$

对于给定集合，求解答案等价于寻找 $F_k\ge 0$ 的最大 $k$

此处仍然用到了集合包含单调性，对于固定的右端点 $r$ 和 $k$，称 $G_k(r)$ 表示，使得 $F_k(a[l,r])\ge 0$ 的最大 $l$。

然后就是，$G_k$ 是一阶交错（还是二阶交错？），所以可以用 KTT 维护，做到 $O(n\log n)$ 或 $O(n\log^2 n)$，唐。

我写这个做法之前还以为这个做法没有用集合包含单调性，没想到其使用了。诶，那这个做法剩下的内容就不是很有意义了。