s062.
PJ. And Reachability
Content
Toad Pimple 有一個整數陣列 $a_1,a_2,…,a_n$ 。
我們稱 $y$ 可從 $x$ 到達，如果 $x<y$ 並且存在整數數組 p 使得 $x=p_1<p_2<…<p_k=y$ 和 $a_{pi}$ & $a_{pi+1}>0$ 對所有整數 $i$ 滿足 $1≤i<k$ 。
這裡 & 表示 bitwise AND operation.
給定 $q$ 對索引，檢查每對索引的可達性。
Input
第一行包含兩個整數 $n$ 和 $q$ ( $2≤n≤300000$ , $1≤q≤300000$ ) — 陣列中整數的數量和你需要回答的查詢的數量。
第二行包含 $n$ 個空格分隔的整數 $a_1,a_2,…,a_n$ ( $0≤ai≤300000$ ) — 給定的陣列。
接下來的 $q$ 行每行包含兩個整數。其中第 i 行包含兩個以空格分隔的整數 $x_i$ 和 $y_i$ ( $1≤x_i<y_i≤n$ )。你需要檢查 $y_i$ 是否可從 $x_i$ 到達。
Output
輸出 $q$ 行。在第 $i$ 行中，如果 $y_i$ 可從 $x_i$ 到達，則列印“ Shi ”，否則列印“ Fou ”。
Sample Input
#1
5 3 1 3 0 2 1 1 3 2 4 1 4
Sample Output
#1
Fou Shi Shi
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (5%): 0.1s , <10M
不公開 測資點#1 (5%): 0.1s , <10M
不公開 測資點#2 (5%): 0.1s , <10M
不公開 測資點#3 (5%): 0.1s , <10M
不公開 測資點#4 (5%): 0.1s , <10M
不公開 測資點#5 (5%): 0.1s , <10M
不公開 測資點#6 (5%): 0.1s , <10M
不公開 測資點#7 (5%): 0.1s , <10M
不公開 測資點#8 (5%): 0.1s , <10M
不公開 測資點#9 (5%): 0.1s , <10M
不公開 測資點#10 (5%): 0.1s , <10M
不公開 測資點#11 (5%): 0.1s , <10M
不公開 測資點#12 (5%): 0.1s , <10M
不公開 測資點#13 (5%): 0.1s , <10M
不公開 測資點#14 (5%): 0.1s , <10M
不公開 測資點#15 (5%): 0.1s , <10M
不公開 測資點#16 (5%): 0.1s , <10M
不公開 測資點#17 (5%): 0.1s , <10M
不公開 測資點#18 (5%): 0.1s , <10M
不公開 測資點#19 (5%): 0.1s , <10M
不公開 測資點#0 (5%): 0.1s , <10M
不公開 測資點#1 (5%): 0.1s , <10M
不公開 測資點#2 (5%): 0.1s , <10M
不公開 測資點#3 (5%): 0.1s , <10M
不公開 測資點#4 (5%): 0.1s , <10M
不公開 測資點#5 (5%): 0.1s , <10M
不公開 測資點#6 (5%): 0.1s , <10M
不公開 測資點#7 (5%): 0.1s , <10M
不公開 測資點#8 (5%): 0.1s , <10M
不公開 測資點#9 (5%): 0.1s , <10M
不公開 測資點#10 (5%): 0.1s , <10M
不公開 測資點#11 (5%): 0.1s , <10M
不公開 測資點#12 (5%): 0.1s , <10M
不公開 測資點#13 (5%): 0.1s , <10M
不公開 測資點#14 (5%): 0.1s , <10M
不公開 測資點#15 (5%): 0.1s , <10M
不公開 測資點#16 (5%): 0.1s , <10M
不公開 測資點#17 (5%): 0.1s , <10M
不公開 測資點#18 (5%): 0.1s , <10M
不公開 測資點#19 (5%): 0.1s , <10M
Hint ：
在第一個例子中， $a_3=0$ 。你無法到達它，因為它與 $a_2$ & $a_4>0$ 的 $AND$ 運算結果總是零。 $a_2$ & $a_4>0$，所以 $4$ 可以從 $2$ 到達，而要從 $1$ 到達 $4$ ，你可以使用 $p=[1,2,4]$ 。
Tags:
出處:
[管理者：
chenwei98050
...
(陳維（Z）)
]
| ID | User | Problem | Subject | Hit | Post Date |
|
沒有發現任何「解題報告」
|
|||||