题目链接
题目大意：给定一个长度为n的数列A,q次询问下标在[l,r]之间所有数的mex.对于非负整数组成的集合S,mex(S)等于最小的不属于集合S的非负整数.
题解：首先离线，按照左端点对询问排序
容易发现，用mex(i)表示1–i的mex，这个mex是单调的，扫一遍就能求了。这样就解决了所有L为1的询问
类似莫队的思想，考虑 [L,R]和[L+1,R] [ L , R ] 和 [ L + 1 , R ] 答案的区别
令nex[i]表示a[i]下一次出现的位置，显然是l到next[l]-1这一段所有sg值大于a[l]的变为a[l] ,线段树区间取min，单点查询即可
区间取min直接暴力改叶节点（segment beats？不会……）
注意：线段树中的叶子节点表示区间[now,i]的mex值(其中now为当前左端点，i为叶节点对应的位置)，线段树中的非叶子节点并没有实际含义，只是为了修改操作的方便，所以不需要pushup
其实可以直接莫队暴力过…… 3585是一样的，直接无视掉大于n的数就行了(区间长度最大为n)
我的收获：半莫队（雾
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f #define M 200005 #define ls x<<1 #define rs x<<1|1 #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 #define root 1,n,1 int n,m,a[M]; int nex[M],last[M],ans[M],sg[M]; int mi[M<<2]; bool mark[M]; struct que{int x,y,id;}q[M]; bool cmp(que a,que b){return a.x<b.x;} void pushdown(int x,int m) { if(mi[x]==INF||m==1) return ; mi[ls]=min(mi[ls],mi[x]); mi[rs]=min(mi[rs],mi[x]); mi[x]=INF; } void build(int l,int r,int x) { mi[x]=INF; if(l==r){mi[x]=sg[l];return ;} int m=(l+r)>>1; build(lson),build(rson); } void updata(int L,int R,int v,int l,int r,int x) { if(l==L&&r==R){mi[x]=min(mi[x],v);return ;} pushdown(x,r-l+1); int m=(l+r)>>1; if(R<=m) updata(L,R,v,lson); else if(L>m) updata(L,R,v,rson); else {updata(L,m,v,lson),updata(m+1,R,v,rson);} } int query(int k,int l,int r,int x){ if(l==r) return mi[x]; pushdown(x,r-l+1); int m=(l+r)>>1; if(k<=m) return query(k,lson); if(k>m) return query(k,rson); } void work() { for(int i=1,now=1;i<=m;i++){ while(now<q[i].x){ if(!nex[now]) nex[now]=n+1; updata(now,nex[now]-1,a[now],root); now++; } ans[q[i].id]=query(q[i].y,root); } for(int i=1;i<=m;i++) printf("%d\n",ans[i]); } void init() { cin>>n>>m; for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>n) a[i]=n;} for(int i=1,k=0;i<=n;i++){ mark[a[i]]=1; if(a[i]==k) while(mark[k]) k++; sg[i]=k; }build(root); for(int i=n;i>=1;i--) nex[i]=last[a[i]],last[a[i]]=i; for(int i=1;i<=m;i++) scanf("%d%d",&q[i].x,&q[i].y),q[i].id=i; sort(q+1,q+1+m,cmp); } int main() { init(); work(); return 0; }