問題一覧 > 通常問題

No.2901 Logical Sum of Substring

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : hahho / テスター : None Liwei Cai cai_lw
お気に入りにしたユーザー ProblemId : 10876 / 自分の提出
問題文最終更新日: 2024-12-11 13:27:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 447 オムニバス (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。