3585: mex

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 918  Solved: 481
[Submit][Status][Discuss]

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

http://www.lydsy.com/JudgeOnline/problem.php?id=3585

思路:

其实这题的思路和bzoj 3339完全就一样啊,连离散化都不需要。->我的bzoj3339:http://www.cnblogs.com/heimao5027/p/6668367.html

因为对于n个数字,他的mex一定是<=n的,所以就算a[i]=1e9,那么我们就不要放到mex函数里面就好了,然后直接令next[i]=n+1即可,并不需要离散化

于是就这么简单的修改一下3339的代码,一下子就又过了= =

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker,"/STACK:102400000,102400000")
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
vector<pair<int, int> > ve[maxn];
int tree[maxn << ], lazy[maxn << ];
int n, q;
int a[maxn], mex[maxn];
bool vis[maxn];
int nxt[maxn], pos[maxn]; void build_tree(int l, int r, int o){
lazy[o] = -;
if (l == r){
tree[o] = mex[l]; return ;
}
int mid = (l + r) / ;
build_tree(l, mid, o << );
build_tree(mid + , r, o << | );
tree[o] = min(tree[o << ], tree[o << | ]);
} void push_down(int o){
int lb = o << , rb = o << | ;
if (lazy[lb] == - || lazy[lb] > lazy[o]){
lazy[lb] = lazy[o];
tree[lb] = min(tree[lb], lazy[lb]);
}
if (lazy[rb] == - || lazy[rb] > lazy[o]){
lazy[rb] = lazy[o];
tree[rb] = min(tree[rb], lazy[rb]);
}
tree[o] = -;
} int query(int x, int l, int r, int o){
if (x == l && x == r){
return tree[o];
}
if (lazy[o] != -) push_down(o);
int mid = (l + r) / ;
if (x <= mid) return query(x, l, mid, o << );
if (x > mid) return query(x, mid + , r, o << | );
} void update(int ql, int qr, int l, int r, int o, int val){
if (ql <= l && qr >= r){
if (lazy[o] == -) lazy[o] = val;
lazy[o] = min(lazy[o], val);
tree[o] = min(lazy[o], tree[o]);
return ;
}
if (lazy[o] != -)push_down(o);
int mid = (l + r) / ;
if (ql <= mid) update(ql, qr, l, mid, o << , val);
if (qr > mid) update(ql, qr, mid + , r, o << | , val);
tree[o] = min(tree[o << ], tree[o << | ]);
}
int ans[maxn];
void solve(){
build_tree(, n, );
for (int i = ; i <= n; i++){
for (int j = ; j < ve[i].size(); j++){
int pos = ve[i][j].fi, id = ve[i][j].se;
ans[id] = query(pos, , n, );
}
int lb = i + , rb = nxt[i] - ;
if (lb <= rb) update(lb, rb, , n, , a[i]);
}
for (int i = ; i <= q; i++){
printf("%d\n", ans[i]);
}
} int main(){
cin >> n >> q;
for (int i = ; i <= n; i++) {
scanf("%d", a + i);
if (a[i] <= n + ) vis[a[i]] = true;
mex[i] = mex[i - ];
while (vis[mex[i]]) mex[i]++;
pos[i] = n + ;
}
for (int i = ; i <= n; i++) pos[i] = n + ;
for (int i = n; i >= ; i--){
if (a[i] >= n + ){
nxt[i] = n + ; continue;
}
nxt[i] = pos[a[i]];
pos[a[i]] = i;
}
for (int i = ; i <= q; i++){
int l, r; scanf("%d%d", &l, &r);
ve[l].pb(mk(r, i));
}
solve();
return ;
}
05-11 22:41