4455. interval

【题目背景】

在此键入。

【题目描述】

对于一个序列 $[a_0,a_1,a_2,\dots,a_{n-1}]$，可以进行如下操作。

    选择两个不同的 $i,j$，满足 $0\le i,j\le n-1$，满足 $a_{i}=a_{j}$，令 $a_i\gets a_i+1$。

给你两个序列 $a,b$，长度均为 $n$，满足 $\forall i\in[0,n-1],a_i\le b_i$。

有 $q$ 次询问，每次询问给出 $0\le l\le r\le n-1$，求出 $[a_l,a_{l+1},\dots,a_{r-1},a_{r}]$ 能否通过若干次操作变成 $[b_l,b_{l+1},\dots,b_{r-1},b_r]$。

【输入格式】

第一行两个正整数 $n,q$，表示数组 $a,b$ 的长度和询问的个数。

接下来 $n$ 行一行两个数，表示 $a_i,b_i$。

接下来 $q$ 行，每行两个正整数表示询问 $l,r$。

【输出格式】

输出一行用空格隔开的 $q$ 个整数，表示每个询问的答案，具体的，对于每个询问，如果答案是能，输出 $1$ 否则输出 $0$。

【样例输入1】

4 3
2 2
1 1
1 3
2 3
0 1
0 3
1 3

【样例输出1】

1 1 0

【样例输入2】

5 5
1 2
2 3
1 1
2 4
1 2
0 2
0 4
1 3
1 4
2 3

【样例输出2】

1 1 0 1 0

【样例说明】

对于样例 $1$：

$[0,1]$ 是一个绝妙区间。这是因为两个数组 $A[0],A[1]$ 和 $B[0],B[1]$ 是相等的。

$[0,3]$ 是一个绝妙区间。这是因为可以通过执行以下操作，使 [$2$, $1$, $1$, $2$] 变为 [$2$, $1$, $3$, $3$]。

选择 $i = 3$，$j = 0$ 并执行操作。操作后数组变为 $[2,1,1,3]$。

选择 $i = 2$，$j = 1$ 并执行操作。操作后数组变为 $[2,1,2,3]$。

选择 $i = 2$，$j = 0$ 并执行操作。操作后数组变为 $[2,1,3,3]$。

$[1,3]$ 不是一个绝妙区间。可以证明，无论如何执行操作，都无法使 $[1,1,2]$ 变为 $[1,3,3]$。

对于样例 $2$：

在所有区间中，绝妙区间为 $[0,2],[0,3],[0,4],[1,4],[2,2]$。

大样例。

【数据规模与约定】

对于全部的数据，满足 $1\le n,q\le 250000,1\le a_i\le b_i\le 10^9,0\le l_i\le r_i\le n-1$。

【来源】

在此键入。