猜测一些结论，不难发现 $A_i=B_i$ 的点是特殊的，他们存在的价值即改变其他 $A_j$，考虑如果 $A_j\to B_j$ 合法，则 $[A_j,B_j)$ 内所有数都在 $A_i=B_i$ 的 $B_i$ 中出现过。

显然不对，因为我们可以让 $A_i$ 变大的过程中让它变成 $A_i=B_i$，这样他就能当跳板了，不难发现对于一堆相同的 $A_i$，最后总有一个 $A_i$ 是无法变大的，如果此时这个 $A_i\ne B_i$，则不合法。

考虑再次猜测结论，合法当且仅当 $\cup_{i=l}^r [A_i,B_i)=\{B_i|i\in [l,r]\}$。

首先，若存在 $x\in [A_i,B_i)$ 但 $x\ne B_j$，则不难发现当 $A_i$ 们变到 $x$ 的时候，他们都要变成 $x+1$，但必须有一个 $A_i$ 留下来，方案不合法。我们考虑在这种条件下构造一组合法方案，每次选出一个最小的 $A_i$，此时一定存在一个 $A_j=B_j$，我们就能令 $A_i\gets A_i+1$，最终一定能完成操作。

为了美观，我们写成 $\cup_{i=l}^r [A_i,B_i]=\{B_i|i\in [l,r]\}$。

不难发现，前者包含后者，所以后者等于前者的充要条件是集合大小相同。

后者的集合大小是区间数颜色，利用扫描线算法加树状数组可以 $O(n\log n)$ 完成。

前者是区间线段并（这部分是弱化版 P8512），考虑扫描线，每次 $r-1\to r$ 时就将 $[A_i,B_i]$ 推平，注意到我们只有推平和查询操作，考虑用 ODT 来维护，根据经典结论 $r$ 在 $1\to n$ 的过程中，往 ODT 插入的颜色段数是 $O(n)$ 的。

考虑将 $[A_i,B_i]$ 推平的时候涂上颜色 $i$，并实时维护 $v_j$ 表示颜色为 $j$ 的颜色段长度之和。

每次推平，要做删除操作，因为整个过程总段数是 $O(n)$ 的，所以我们可以暴力遍历这些颜色段，并修改对应颜色的 $v_i$，然后删除，再新加入的颜色段的信息。

对于询问 $[L,R]$，当 $r$ 扫到 $R$ 时，我们要查询的就是 $\sum_{i=L}^R v_i$，可以用树状数组快速维护。

时间复杂度为 $O((n+q)\log n)$，和值域无关。