题意：
求任意一个区间的SG函数。
想到线段树，但是线段树合并很麻烦。
线段树——分块。
分块的一个应用就是莫队算法。
怎么暴力递推呢？
从一个区间到另一个区间，Ans 取决于 Ans 和 加入和删除的这个数的大小比较。加入一个新数，可能导致Ans 变大，变到哪里去呢？ 用一个cnt记录出现数值的个数。
变大到cnt=0的地方。
减去一个数，可能导致Ans 变小。这时就要看cnt 和 大小比较了。
#include <bits/stdc++.h>using namespace std;const int maxn = 200011*41;int N,M; int a[maxn]; int pos[maxn]; int ans[maxn]; int cnt[maxn];int Ans;struct Node {int l,r;int id; }nodes[maxn];bool cmp(Node a,Node b) {if(pos[a.l]==pos[b.l])return a.r < b.r;return pos[a.l] < pos[b.l]; }void add(int x) {cnt[x]++;if(Ans==x)while(cnt[Ans])Ans++; }void del(int x) {cnt[x]--;if(cnt[x]==0&&x<Ans)Ans=x; }int main(int argc, char const *argv[]) {scanf("%d%d",&N,&M);int sz =ceil(sqrt(1.0*N));for(int i=1; i <=N; i++) {scanf("%d",&a[i]);pos[i] = (i-1)/sz;}for(int i=1; i <= M; i++) {scanf("%d%d",&nodes[i].l,&nodes[i].r);nodes[i].id = i;}sort(nodes+1,nodes+1+M,cmp);int L = 1,R = 0;Ans = 0;for(int i=1;i<=M;i++){int id = nodes[i].id;while(R<nodes[i].r)R++,add(a[R]);while(L>nodes[i].l)L--,add(a[L]);while(R>nodes[i].r)del(a[R]),R--;while(L<nodes[i].l)del(a[L]),L++;ans[id]=Ans;}for(int i=1; i <= M; i++)printf("%d\n", ans[i]);return 0; }
