题解：分块维护权值，用莫队转移。

分块修改操作$O(1)$，查询$O(\sqrt{A_{max}})$。莫队转移$O(m\sqrt n)$。总共是$O(m\sqrt n)$

一份代码解决两道题。额外的经验！

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 inline char nc() { 7     static char b[1<<14],*s=b,*t=b; 8     return s==t&&(t=(s=b)+fread(b,1,1<<14,stdin),s==t)?-1:*s++; 9 }10 inline void read(int &x) {11     char b = nc(); x = 0;12     for (; !isdigit(b); b = nc());13     for (; isdigit(b); b = nc()) x = x * 10 + b - '0';14 }15 int n, m, a[200010], ans[200010];16 int S, bl[200010], tans, cnt[200010];17 struct Q {18     int l, r, id, t;19     inline void init(int i) {20         read(l); read(r); id = i; t = l / S;21     }22     inline bool operator<(const Q &q) const {23         return t < q.t || (t == q.t && r < q.r);24     }25 } q[200010];26 const int INF = 0x3f3f3f3f;27 void edt(int x, int k) {28     if (x > n) return; cnt[x] += k;29     if (x < tans && !cnt[x]) tans = x;30     while (cnt[tans]) ++tans;31 }32 int main() {33     read(n); read(m); S = sqrt(n);34     for (int i = 1; i <= n; ++i) read(a[i]);35     for (int i = 0; i <= n; ++i) bl[i] = i / S + 1;36     for (int i = 0; i < m; ++i) q[i].init(i);37     sort(q, q + m); edt(a[1], 1);38     for (int l = 1, r = 1, i = 0; i < m; ++i) {39         while (l < q[i].l) edt(a[l++], -1);40         while (l > q[i].l) edt(a[--l], 1);41         while (r < q[i].r) edt(a[++r], 1);42         while (r > q[i].r) edt(a[r--], -1);43         ans[q[i].id] = tans;44     }45     for (int i = 0; i < m; ++i) printf("%d\n", ans[i]);46     return 0;47 }