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
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
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 ;
}