题目描述
有一个长度为n的数组{a1,a2,…,an}。m次询问,每次询问一个区间内最小没有出现过的自然数。
输入格式
第一行n,m。
第二行为n个数。
从第三行开始,每行一个询问l,r。
输出格式
一行一个数,表示每个询问的答案。
一开始以为像答案这样的做法会超时,没想到真是这样写。。。
1 #include<cstdio> 2 #include<algorithm> 3 #include<math.h> 4 #include<string.h> 5 using namespace std; 6 const int maxn=2e5+10; 7 int num[maxn]; 8 int answer,block; 9 int vis[maxn]; 10 struct node 11 { 12 int l,r,id; 13 int Ans; 14 }ans[maxn]; 15 bool cmp(node x,node y) 16 { 17 if(x.l/block!=y.l/block) 18 return x.l<y.l; 19 if(x.l/block&1) //使用波形排序,可进一步的优化 20 return x.r<y.r; 21 return x.r>y.r; 22 } 23 bool CMP(node x,node y) 24 { 25 return x.id<y.id; 26 } 27 void Delete(int pos) 28 { 29 vis[num[pos]]--; 30 if(!vis[num[pos]]&&num[pos]<answer){ 31 answer=num[pos]; 32 } 33 } 34 void add(int pos) 35 { 36 vis[num[pos]]++; 37 if(vis[num[pos]]==1&&answer==num[pos]){ 38 int tmp=answer+1; 39 while(1){ 40 if(!vis[tmp]){ 41 answer=tmp; 42 return; 43 } 44 tmp++; 45 } 46 } 47 } 48 int main() 49 { 50 int n,m; 51 scanf("%d%d",&n,&m); 52 block=sqrt(n); 53 for(int i=1;i<=n;i++) scanf("%d",&num[i]); 54 for(int i=1;i<=m;i++){ 55 scanf("%d%d",&ans[i].l,&ans[i].r); 56 ans[i].id=i; 57 } 58 sort(ans+1,ans+1+m,cmp); 59 int left=1,right=0; 60 for(int i=1;i<=m;i++){ 61 while(ans[i].l>left) Delete(left++); 62 while(ans[i].l<left) add(--left); 63 while(ans[i].r>right) add(++right); 64 while(ans[i].r<right) Delete(right--); 65 ans[i].Ans=answer; 66 } 67 sort(ans+1,ans+1+m,CMP); 68 for(int i=1;i<=m;i++) 69 printf("%d\n",ans[i].Ans); 70 return 0; 71 }