No.2901 Logical Sum of Substring
Problem Statement
You are given an integer sequence $A$ of length $N$. You are also given $Q$ queries; process them in order.
There are two types of queries:
1 i v: Replace $A_i$ with $v$.2 l r: Determine whether $[A_l,\ A_{l+1},\ldots,\ A_r]$ has a contiguous subarray whose logical sum (bitwise OR) is equal to $2^K-1$, and if so, output the length of the shortest contiguous subarray satisfying the condition.
Note: Three hints are available on the editorial page, so please refer to them if you get stuck.
Input
$N \enspace K$
$A_1 \enspace A_2\ \ldots\ A_N$
$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq 16$
- $1 \leq Q \leq 10^4$
- Every $v \in A$ satisfies $0 \leq v < 2^K$
- Every query of type 1 satisfies $1 \leq i \leq N$ and $0 \leq v < 2^K$
- Every query of type 2 satisfies $1 \leq l \leq r \leq N$
- All input values are integers
Output
For each query of type 2, output on its own line the length of the shortest contiguous subarray if one satisfying the condition exists, or -1 otherwise.
Sample
Sample 1
Input
3 2 1 2 3 4 2 1 2 2 1 3 1 2 1 2 1 2
Output
2 1 -1
For clarity, values are written in binary. Initially, $A=[01, 10, 11]$.
In the 1st query, the logical sum of $01$ and $10$ is $11$, so the contiguous subarray $[01, 10]$ satisfies the condition. On the other hand, $[01]$ and $[10]$ do not satisfy it. Therefore, output the length 2.
In the 2nd query, the contiguous subarray $[11]$ satisfies the condition, so output the length 1.
In the 3rd query, replace the 2nd element of $A$ with $1$. This makes $A=[01, 01, 11]$.
In the 4th query, no contiguous subarray of $[01, 01]$ satisfies the condition, so output -1.
Sample 2
Input
6 4 14 12 15 12 13 11 10 2 1 2 1 3 4 1 2 6 1 5 5 2 4 6 1 5 15 1 3 3 2 1 5 1 3 11 2 2 4
Output
-1 2 1 2
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hahho
cai_lw