P15585 [KTSC 2026] Wonderful Interval 2 / Wonderful Interval 2

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: ```cpp vector array_operation(vector A, vector B, vector L, vector 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.

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]$

The sample grader prints the answer in the following format: * Line $1$: the return value of `array_operation`

### 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 | ID | Score | Constraints | | :-: | :-: | :- | | $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$ | No additional constraints | ### 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