B - AND
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
長さ n\geq 2 の非負整数列 a=(a_1,a_2,\ldots,a_n) について、f(a) を以下の値として定義します。
- 次の操作を行って a の全ての要素を 0 に等しくできるならば、そうするために必要な操作回数の最小値。できないならば -1。
- 1\leq i\leq n,1\leq j\leq n,|i-j|=1 を満たす整数 i,j を選ぶ。a_i を a_i\operatorname{AND}a_j で置き換える。
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。Q 個のクエリを処理してください。
i 番目のクエリでは整数 L_i,R_i が与えられるので、f((A_{L_i},A_{L_i+1},\ldots,A_{R_i})) を求めてください。
AND の定義
非負整数 x,y に対し、ビットごとの論理積 x\operatorname{AND}y は以下のように定義されます。- x\operatorname{AND}y を 2 進法で表現したときの 2^k の位の数は、x と y を2 進法で表現したときの 2^k の位の数がともに 1 である場合 1 で、そうでない場合 0。
制約
- 2\leq N\leq 2\times 10^5
- 0\leq A_i\lt 2^{30}
- 1\leq Q\leq 2\times 10^5
- 1\leq L_i\lt R_i\leq N
入力
入力は以下の形式で標準入力から与えられます。
N A_1 A_2 \ldots A_N Q L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
各クエリで求めた値を改行区切りで出力してください。
入力例 1
3 5 6 11 2 1 3 2 3
出力例 1
4 -1
1 番目のクエリでは、a=(5,6,11) として f(a) の値を出力します。a が (5,6,11)\rightarrow(5,4,11)\rightarrow(5,0,11)\rightarrow(5,0,0)\rightarrow(0,0,0) と変化するように操作を行うと、4 回の操作で a の要素を全て 0 と等しくできます。4 回より少ない操作手順は存在しないことが証明できるので、f(a)=4 となります。
2 番目のクエリでは、a=(6,11) として f(a) の値を出力します。どのように操作を行っても a の全ての要素を 0 と等しくすることはできないことが証明できるので、f(a)=-1 となります。
入力例 2
10 1017 40 583 310 485 428 726 123 143 962 10 2 3 2 10 3 10 5 8 5 6 5 6 3 8 6 7 1 9 1 9
出力例 2
2 9 9 5 -1 -1 7 -1 9 9