Problem Description

Youngwoo has two arrays $A, B$ of length $N$. For any $0 \le i \le N - 1$, we have $A[i] \le B[i]$.

An interval $[l, r]$ is a wonderful interval if and only if it satisfies all of the following conditions:

• $l, r$ are integers.
• $0 \le l \le r \le N - 1$.
• By repeatedly performing the following operation, $[A[l], \cdots, A[r]]$ can be transformed into $[B[l], \cdots, B[r]]$:
  • Let the current array be $X = [X[0], X[1], \cdots, X[r - l]]$.
  • Choose two distinct integers $i, j$ ($0 \le i, j \le r - l$) such that $X[i] = X[j]$, and then set $X[i] \gets X[i] + 1$.

Youngwoo is curious about which intervals are wonderful intervals. Specifically, Youngwoo is given $Q$ queries, numbered $0 \sim Q - 1$, represented by two arrays $L, R$ of length $Q$.

Query $j$ ($0 \le j \le Q - 1$) asks whether the interval $[L[j], R[j]]$ is a wonderful interval.

Write a program to answer Youngwoo’s queries.

Implementation Details

This is a functional interactive problem. You do not need to, and should not, implement the main function.

You should implement the following function:

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

• $A, B$: integer arrays of size $N$.
• $L, R$: integer arrays of size $Q$.
• Return an integer array $S$ of size $Q$. If $[L[j], R[j]]$ is a wonderful interval, then $S[j]$ should be $1$, otherwise $0$ ($0 \le j \le Q - 1$).
• This function is called exactly once.

Your source code should not call any input/output functions.

Input Format

The input format of the sample grader is as follows:

• Line $1$: $N$ $Q$
• For all $0 \le i \le N - 1$:
  • Line $2 + i$: $A[i]$ $B[i]$
• For all $0 \le i \le Q - 1$:
  • Line $2 + N + i$: $L[i]$ $R[i]$

Output Format

The sample grader prints the answer in the following format:

• Line $1$: the return value of 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

Hint

Constraints

• $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$).

Subtasks

Samples

Sample 1

Consider the following call:
array_operation([2, 1, 1, 2], [2, 1, 3, 3], [0, 0, 1], [1, 3, 3])

• [$0$, $1$] is a wonderful interval. This is because the two arrays $A[0]$, $A[1]$ and $B[0]$, $B[1]$ are equal.
• [$0$, $3$] is a wonderful interval. This is because by performing the following operations, [$2$, $1$, $1$, $2$] can be changed into [$2$, $1$, $3$, $3$].
  • Choose $i = 3$, $j = 0$ and perform the operation. After the operation, the array becomes [$2$, $1$, $1$, $3$].
  • Choose $i = 2$, $j = 1$ and perform the operation. After the operation, the array becomes [$2$, $1$, $2$, $3$].
  • Choose $i = 2$, $j = 0$ and perform the operation. After the operation, the array becomes [$2$, $1$, $3$, $3$].
• [$1$, $3$] is not a wonderful interval. It can be proven that no matter how you perform the operations, it is impossible to change [$1$, $1$, $2$] into [$1$, $3$, $3$].

Therefore, the function should return [$1$, $1$, $0$].

Sample 2

Consider the following call:
array_operation([1, 2, 1, 2, 1], [2, 3, 1, 4, 2], [0, 0, 1, 1, 2], [2, 4, 3, 4, 3])

Among all intervals, the wonderful intervals are [$0$, $2$], [$0$, $3$], [$0$, $4$], [$1$, $4$], [$2$, $2$]. Therefore, the function should return [$1$, $1$, $0$, $1$, $0$].

Translated by ChatGPT 5