BZOJ 3339: Rmq Problem 莫队水题

2019-11-08 00:54:40

字体：大中小

来源：转载

供稿：网友

题目链接：点这里题意： n个数，m次询问l，r。查询区间mex是什么。解题方法：莫队水题。

#include <bits/stdc++.h>using namespace std;const int maxn = 1000010;int a[maxn], pos[maxn], c[maxn], Ans[maxn];int n, m, ans;struct Q{int l, r, id; } q[maxn];bool cmp(Q a, Q b){ if(pos[a.l] == pos[b.l]) return a.r < b.r; return pos[a.l] < pos[b.l];}void add(int x){ c[x]++; if(ans == x) while(c[ans]) ans++;}void del(int x){ c[x]--; if(c[x] == 0 && x < ans) ans = x;}int main(){ scanf("%d%d", &n, &m); int block = sqrt(n); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); pos[i] = (i - 1) / block; } for(int i = 1; i <= m; i++){ scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; } sort(q + 1, q + m + 1, cmp); int L = 1, R = 0; ans = 0; for(int i = 1; i <= m; i++){ int id = q[i].id; while(R < q[i].r) R++, add(a[R]); while(L > q[i].l) L--, add(a[L]); while(R > q[i].r) del(a[R]), R--; while(L < q[i].l) del(a[L]), L++; Ans[id] = ans; } for(int i = 1; i <= m; i++){ PRintf("%d/n", Ans[i]); } return 0;}

上一篇：leecode 解题总结：200. Number of Islands

下一篇：js内存泄露问题