bzoj 3585: mex && 3339: Rmq Problem — 主席树

  • 2017-04-27
  • 0
  • 0

 

3585: mex

Time Limit: 20 Sec  Memory Limit: 128 MB

Description

  有一个长度为n的数组{a1,a2,…,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。

Input

  第一行n,m。
第二行为n个数。
从第三行开始,每行一个询问l,r。

Output

  一行一个数,表示每个询问的答案。

Sample Input

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5

Sample Output

1
2
3
0
3

HINT

 

数据规模和约定

对于100%的数据:

1<=n,m<=200000

0<=ai<=109

1<=l<=r<=n

对于30%的数据:

1<=n,m<=1000

 

Source

By 佚名提供

 

我们考虑建权值线段树,每个数字 x 保存它最后出现的位置

这样查询[l,r],就是找第r棵主席树中第一个值< l 的

主席树上每个区间维护当前数中,权值从 l 到 r 中最后一次出现最靠左的位置

就是相当于维护区间最小值即可

 

评论

还没有任何评论,你来说两句吧