前言

更可爱的阅读体验

思路

先拆一下题目里的条件。令被矩形包含的所有点的 hih_i 构成的可重集为 SS，从小到大对 SS 考虑，那么对任意三个相邻的 Si,Si+1,Si+2S_{i},S_{i+1},S_{i+2} 均满足 Si+Si+1≤Si+2S_{i}+S_{i+1}\leq S_{i+2} 是答案为 00 的充要条件。发现 SS 中的元素增长得很快，因为值域有限制，尝试构造出一个最大的答案为 00 的 SS，满足 Si+2=Si+1+SiS_{i+2}=S_{i+1}+S_i。其实这个时候 SS 里的数就是斐波那契数列 FF，由于 F45>109F_{45}>10^9，我们得到了当 ∣S∣≥45|S|\geq 45 时答案必然为 11。

做一遍矩形数点排除掉 ∣S∣≥45|S|\geq 45 的询问后，我们直接将每个点插入将其包含的剩下的询问中。这个过程可以用扫描线 + 线段树实现，对线段树每个节点开个 set，扫到一个询问 xx 轴的左端点时将其插入进线段树上 yy 轴对应的区间里，在 xx 轴的右端点再删除，扫到点的时候就在线段树上从根到其 yy 坐标对应的叶子走一遍。然后对每个询问暴力 check 是否合法即可。

复杂度 O(qlog⁡qlog⁡n+qlog⁡V)\mathcal{O}(q\log q\log n+q\log V)。