e732: A Simple RMQ Problem
Tags : KD樹 RMQ 樹套樹
Accepted rate : 4人/7人 ( 57% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-11-23 21:00

Content

給定一個長為n的序列,多次詢問[l,r]中最大且只出現一次的數。

如果沒有這樣的數,請輸出0

Input

測資第一行為兩個正整數N,M 。M 是詢問數,N 是序列的長度(N<=100000 ,M<=200000)

第二行有N個整數a1~aN(皆在int範圍內)

再來有M行,每行兩個正整數l,r(l,r<=N)

Output

[l,r]中最大且只出現一次的數。

如果沒有這樣的數,請輸出0

Sample Input
10 10
6 4 9 10 9 10 9 4 10 4
3 8
10 1
3 4
9 4
8 1
7 8
2 9
1 1
7 3
9 9
Sample Output
4
6
10
4
6
9
0
6
0
10
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (50%): 1.0s , <10M
公開 測資點#1 (50%): 1.0s , <1K
Hint :

 BZOJ3489

Tags:
KD樹 RMQ 樹套樹
出處:
π [管理者:
314159265358979... (少年π)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」