首先我们可以想到离线，于是什么线段树啊随便维护一下就好了
然后我比较傻，只会莫队。。。
由于ans ≤ n，我们可以对ans分块，于是每次修改的复杂度是O(1)的，询问的复杂度是O(√n)
总复杂度O(m√n + n√n)
1 /************************************************************** 2 Problem: 3585 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:9756 ms 7 Memory:7068 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cmath> 12 #include <algorithm> 13 14 using namespace std; 15 const int N = 200005; 16 const int B = 505; 17 18 int n, Q; 19 int sz, cnt_block; 20 int a[N], b[N], cnt[N], st[B]; 21 int l, r, block_cnt[N], ans[N]; 22 23 struct query{ 24 int l, r, w; 25 26 inline bool operator < (const query x) const { 27 return b[l] == b[x.l] ? r < x.r : b[l] < b[x.l]; 28 } 29 } q[N]; 30 31 inline int read() { 32 int x = 0; 33 char ch = getchar(); 34 while (ch < '0' || '9' < ch) 35 ch = getchar(); 36 while ('0' <= ch && ch <= '9') { 37 x = x * 10 + ch - '0'; 38 ch = getchar(); 39 } 40 return x; 41 } 42 43 void update(int x, int del) { 44 if (x > n) return; 45 if (cnt[x] == 0) ++block_cnt[b[x]]; 46 cnt[x] += del; 47 if (cnt[x] == 0) --block_cnt[b[x]]; 48 } 49 50 int Query() { 51 int i; 52 if (!cnt[0]) return 0; 53 for (i = 1; i <= cnt_block; ++i) 54 if (block_cnt[i] != st[i + 1] - st[i]) break; 55 for (i = st[i]; i < n; ++i) 56 if (!cnt[i]) return i; 57 return n; 58 } 59 60 int main() { 61 int i; 62 n = read(), Q = read(); 63 sz = (int) sqrt(n); 64 if (!sz) sz = 1; 65 for (i = 1; i <= n; ++i) { 66 if (i % sz == 1 || sz == 1) 67 st[++cnt_block] = i; 68 b[i] = cnt_block; 69 } 70 st[cnt_block + 1] = n + 1; 71 72 for (i = 1; i <= n; ++i) a[i] = read(); 73 for (i = 1; i <= Q; ++i) 74 q[i].l = read(), q[i].r = read(), q[i].w = i; 75 sort(q + 1, q + Q + 1); 76 for (i = l = 1, r = 0; i <= Q; ++i) { 77 for (; l < q[i].l; ) update(a[l++], -1); 78 for (; l > q[i].l; ) update(a[--l], 1); 79 for (; r < q[i].r; ) update(a[++r], 1); 80 for (; r > q[i].r; ) update(a[r--], -1); 81 ans[q[i].w] = Query(); 82 } 83 for (i = 1; i <= Q; ++i) 84 printf("%d ", ans[i]); 85 return 0; 86 }
(p.s. 啊太慢什么的。。。这个嘛呵呵呵。。。不要在意这种细节嘛恩恩)