1699 . Problem I 害蟲決戰時刻
TopCoder
Tags
Description
甦蹦這幾天心急如焚！因為他的傳說中的橘子遇到了蟲害！
而且並不是一種蟲，是很多種蟲混雜入侵了橘子園。
如今是決戰的時刻，害蟲們在籬笆前一字排開，準備對橘子園進行總攻擊。
甦蹦腦袋裡想到了一句話，擒賊先擒王。
沒錯，要擊倒害蟲聯軍，就要先把領導的蟲種族找出來。當然，也可能沒有領導種族。
對於每個區段[L, R]的害蟲們，會有一個領導係數K，
表示如果有一種蟲在這個區段內出現大於等於(區段長/K)隻，
那麼代表該區段有領導種族；反之則表示該區段僅是一盤散沙。
現在書蹦想瞭解每個指定區段是否有領導種族，請你幫他解決這個問題吧。
Input Format
輸入第一行有兩個數字N, Q，表示害蟲的數量跟詢問個數。(害蟲編號為1~N)
接下來有一行有N個數字，依序代表每隻害蟲的種族。
接下來會有Q行，每行有三個數字L, R, K，表示區段[L, R]的領導係數為K。
保證N ≤ 50,000，所有詢問的K值總和不超過100,000。
Output Format
輸出包含Q行，每行僅一個字串"Yes"或"No"表示該區段是否有領導種族。
Sample Input 1
5 3
1 2 2 1 3
1 3 2
1 5 2
1 5 3
1 2 2 1 3
1 3 2
1 5 2
1 5 3
Sample Output 1
Yes
No
Yes
No
Yes
Hints
第一筆詢問區間為{1, 2, 2}，係數為2。所以害蟲2為領導。
第二筆詢問區間為{1, 2, 2, 1, 3}，係數為2。所以沒有任何一個領導。
第三筆詢問區間為{1, 2, 2, 1, 3}，係數為3。害蟲1和2都是領導。
甦蹦就算知道了有無領導種族但還是無力對抗害蟲大軍，甦蹦只好前往古墨西哥神殿尋求遠古先靈的協助。於是各路英豪都聚在一起了……
Problem Source
原TIOJ1699 / ABCLS Contest, Problem I
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |