题目描述

英宇有两个长度为 $N$ 的数组 $A,B$。对于任意 $0\le i\le N-1$，有 $A[i]\le B[i]$。

一个区间 $[l,r]$ 是绝妙区间，当且仅当其满足以下所有条件：

• $l,r$ 为整数；
• $0\le l\le r\le N-1$；
• 通过重复以下操作，可以将 $[A[l],\cdots,A[r]]$ 变换为 $[B[l],\cdots,B[r]]$：
  • 令此时的数组为 $X=[X[0],X[1],\cdots,X[r-l]]$。
  • 选择两个不同的整数 $i,j$（$0\le i,j\le r-l$）满足 $X[i]=X[j]$，然后令 $X[i]\gets X[i]+1$。

英宇好奇哪些区间是绝妙区间。具体地，英宇给定了 $Q$ 个询问，编号 $0\sim Q-1$，这些询问用两个长度为 $Q$ 的数组 $L,R$ 来表示。

询问 $j$（$0\le j\le Q-1$）表示，查询区间 $[L[j],R[j]]$ 是否是绝妙区间。

写一个程序回答英宇的询问。

实现细节

这是一道函数式交互题。你不必，也不应实现 main 函数。

你应当实现以下的函数：

vector<int> array_operation(vector<int> A, vector<int> B, vector<int> L, vector<int> R)

• $A,B$：大小为 $N$ 的整数数组。
• $L,R$：大小为 $Q$ 的整数数组。
• 返回一个大小为 $Q$ 的整数数组 $S$。若 $[L[j],R[j]]$ 是绝妙区间，$S[j]$ 应为 $1$，否则为 $0$（$0\le j\le Q-1$）。
• 该函数被调用恰好一次。

你的源代码中不应调用任何输入/输出函数。

输入格式

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$ $Q$
• 对于所有 $0 \le i \le N - 1$：
  • 第 $2 + i$ 行：$A[i]$ $B[i]$
• 对于所有 $0 \le i \le Q - 1$：
  • 第 $2 + N + i$ 行：$L[i]$ $R[i]$

输出格式

示例评测程序按以下格式打印答案：

• 第 $1$ 行：array_operation 的返回值

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

1 1 0

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

1 1 0 1 0

提示

数据范围

• $1\le N,Q\le 250\, 000$；
• $1\le A[i]\le B[i]\le 10^9$（$0\le i\le N-1$）；
• $0\le L[j]\le R[j]\le N-1$（$0\le j\le Q-1$）；

子任务

编号	得分	限制
$1$	$9$	$N,Q\le 100$，$B[i]\le 100$
$2$	$7$	$N,Q\le 2\, 000$，$A[i]=1$
$3$	$16$	$A[i]=1$
$4$	$10$	$N,Q\le 2\, 000$
$5$	$4$	$B[i]\le 2$
$6$	$13$	$B[i]\le 100$
$7$	$31$	$B[i]\le 250\, 000$
$8$	$10$	无额外限制

样例

样例 1

考虑以下调用： array_operation([2, 1, 1, 2], [2, 1, 3, 3], [0, 0, 1], [1, 3, 3])

• [$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$]。

因此，函数应返回 [$1$, $1$, $0$]。

样例 2

考虑以下调用： array_operation([1, 2, 1, 1], [2, 3, 1, 4, 2], [0, 0, 1, 1, 2], [2, 4, 3, 4, 3])

在所有区间中，绝妙区间为 [$0$, $2$], [$0$, $3$], [$0$, $4$], [$1$, $4$], [$2$, $2$]。因此，函数应返回 [$1$, $1$, $0$, $1$, $0$]。