P15585 [KTSC 2026] 绝妙区间 2 / Wonderful Interval 2
题目描述
英宇有两个长度为 $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` 函数。
你应当实现以下的函数：
```cpp
vector array_operation(vector A, vector B, vector L, vector 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` 的返回值
说明/提示
### 数据范围
- $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$]。