CF2163 D2. Diadrash (Hard Version)
有一个隐藏的 \(0\) 到 \(n-1\) 的排列，初始给定 \(n\) 和 \(q\) 个区间 \([l_i,r_i]\)，你可以至多询问 \(30\) 次每次查询排列的一个区间的 \(\mathrm{mex}\)，用来找到这 \(q\) 个区间的 \(\mathrm{mex}\) 的最大值。\(n \leq 10^4,q \leq 3 \times 10^5\)。
首先把被包含的区间踢掉，剩下的区间按 \(l\) 为关键字排序后 \(l,r\) 分别递增。
考虑对于排列 \(\mathrm{mex}\) 的一个性质：\(\mathrm{mex}(l,r)=\mathrm{min}(\mathrm{mex}(1,r),\mathrm{mex}(l,n))\)。那么 \(\mathrm{mex}(1,x),\mathrm{mex}(x,n)\) 两个函数一个不减一个不增，取 \(\mathrm{min}\) 后显然可以三分，注意到是整数函数，可以用二分替代，每次要询问两个函数对应点的值，\(2\mathrm{log}\ n=30\)。
code