a540:
[模板] 整體二分 / 第K小 (Hard Version)
內容
給一個長度為$N$的陣列$A_1,A_2,\dots ,A_N$，之後會有$Q$次詢問，
每次詢問會有三個數字$l_i,r_i,k_i$，請輸出$A$陣列中的左閉右閉區間$[l_i,r_i]$中第$k_i$小的數字是什麼
輸入說明
第一行有兩個數字$N,Q$，即題目中的$N,Q$
第二行有$N$個整數$A_1,A_2,\dots ,A_N$即題目中的$A$陣列
第三行到第$Q+2$行每行三個數字$l_i,r_i,k_i$，詢問$A$陣列中的左閉右閉區間$[l_i,r_i]$中第$k_i$小的數字是什麼
輸出說明
輸出$Q$行，每行包含一個數字，代表第$i$筆詢問的答案
範例輸入
#1
7 3 1 5 2 6 3 7 4 1 7 3 2 5 3 4 4 1
範例輸出
#1
3 5 6
測資資訊：
記憶體限制：
128
MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
對於40%的測資，$N,Q\le 1000,-10^9\le A_i\le 10^9,1\le l_i,r_i \le N,k_i\le r_i-l_i+1$
對於100%的測資，$N,Q\le 10^5,-10^9\le A_i\le 10^9,1\le l_i,r_i \le N,k_i\le r_i-l_i+1$
出處:
洛谷
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||