題目描述
有一個長度為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 } 還有一個權值線段樹的解法：
對于第i棵權值線段樹，維護一下數列前ii項中每個權值出現的最靠右的位置。然後向上更新一下最小值。這樣如果某個權值最靠右的位置都比查詢區間左端點小的話，那它一定沒有在這個區間裡出現。維護最小值目的就是看最小的是否比左端點大，根據這個線上段樹上二分。
權值範圍是10^9109的。題解裡有說答案最大為nn，直接把>n>n的a[i]a[i]處理為n+1n+1就行。蒟蒻沒有想到QAQQAQ，說一下蒟蒻的處理：
用離散化，但是一個權值沒有在數列裡出現過的話就不會在離散化數組中，也不會出現線上段樹中，查詢會出鍋。注意到一個詢問的答案要麼是00，要麼是數列中某個數的值+1+1。這樣離散化時把00和每個出現過的權值+1+1都丢進去就行了QwQQwQ。
當然這道題不強制線上也不修改，可以把詢問離線下來一邊掃一邊加，遇到詢問右端點就查詢左端點，不需要主席樹（可持久化線段樹），一棵權值線段樹就可以了。
1 #include<cstdio>
2 #include<algorithm>
3 #include<math.h>
4 #include<string.h>
5 #include<vector>
6 using namespace std;
7 const int maxn=2e5+10;
8 int ans[maxn];
9 int t; //T為離散化之後的數組長度
10 int a[maxn],b[maxn*2],cnt; //原數組和離散化的數組，以及下标cnt；
11 int tree[maxn<<5];
12 int root[maxn];
13 void update(int root)
14 {
15 tree[root]=min(tree[root<<1],tree[root<<1|1]);
16 }
17 void add(int num,int l,int r,int root,int base)
18 {
19 if(l==r){
20 tree[root]=base;
21 return;
22 }
23 int mid=l+r>>1;
24 if(num<=mid) add(num,l,mid,root<<1,base);
25 else add(num,mid+1,r,root<<1|1,base);
26 update(root);
27 }
28 int query(int pos)
29 {
30 int l=1,r=t;
31 int root=1;
32 while(l<r){
33 int mid=l+r>>1;
34 //如果左區間的值至少存在一個權值的下标小于pos的，就證明此範圍内有符合條件的數；
35 //就像左邊二分；
36 if(tree[root<<1]<pos) r=mid,root=root<<1;
37 //否則向右邊二分；
38 else l=mid+1,root=root<<1|1;
39 }
40 return b[l];
41 }
42 int main()
43 {
44 int n,m;
45 scanf("%d%d",&n,&m);
46 b[++cnt]=0;
47 for(int i=1;i<=n;i++){
48 scanf("%d",&a[i]);
49 b[++cnt]=a[i];
50 b[++cnt]=a[i]+1;
51 }
52 sort(b+1,b+1+cnt);
53 t=unique(b+1,b+1+cnt)-b-1;
54 for(int i=1;i<=n;i++){
55 a[i]=lower_bound(b+1,b+1+t,a[i])-b;
56 add(a[i],1,t,1,i,root[i],root[i-1]);
57 }
58 return 0;
59 } 1 #include<cstdio>
2 #include<algorithm>
3 #include<math.h>
4 #include<string.h>
5 using namespace std;
6 const int maxn=4e5+10;
7 int a[maxn],b[maxn],cnt=0,len;
8 struct node{int l,r,id;}tree[maxn<<5];int cot;
9 //主席樹需要開的空間比一般線段樹更大，另外後面的cot是記錄主席樹節點用的。
10 int Root[maxn];
11 void build(int &x,int l,int r)
12 {
13 //這裡的&x會把x得到的值傳給這個變量，也就是Root[0];
14 //建一波空樹，其實可以不建的，之前打過不建的代碼，
15 //但總覺得不建的話心裡不踏實。啊哈哈哈
16 x=++cot;
17 if(l==r) return ;
18 int mid=l+r>>1;
19 build(tree[x].l,l,mid);
20 build(tree[x].r,mid+1,r);
21 }
22 void add(int num,int l,int r,int &x,int y,int pos)
23 {
24 //同上，這裡的&x會傳給root[i];
25 tree[++cot]=tree[y];
26 x=cot; //将cot傳給x,這個cot儲存的是Root[i]這個節點的值，這個節點是根節點。
27 if(l==r){
28 tree[cot].id=pos;
29 //tree[x].id=pos; 這裡也可以這樣寫
30 return;
31 }
32 int mid=l+r>>1;
33 if(num<=mid) add(num,l,mid,tree[x].l,tree[y].l,pos);
34 else add(num,mid+1,r,tree[x].r,tree[y].r,pos);
35 int left=tree[x].l,right=tree[x].r;
36 tree[x].id=min(tree[left].id,tree[right].id); //傳遞最小值；
37 }
38 int query(int pos,int base)
39 {
40 //這一部分是本題内容。
41 int l=1,r=len;
42 while(l<r){
43 int mid=l+r>>1;
44 //left存儲的是根節點的左區間，right為右區間。
45 int left=tree[base].l,right=tree[base].r;
46 if(tree[left].id<pos) r=mid,base=left;
47 else l=mid+1,base=right;
48 }
49 return b[l];
50 }
51 int main()
52 {
53 int n,m;
54 scanf("%d%d",&n,&m);
55 b[++cnt]=0;
56 for(int i=1;i<=n;i++){
57 scanf("%d",&a[i]);
58 b[++cnt]=a[i];
59 b[++cnt]=a[i]+1;
60 }
61 sort(b+1,b+1+cnt);
62 len=unique(b+1,b+1+cnt)-b-1;
63 build(Root[0],1,len);
64 for(int i=1;i<=n;i++){
65 a[i]=lower_bound(b+1,b+1+len,a[i])-b;
66 add(a[i],1,len,Root[i],Root[i-1],i);
67 }
68 for(int i=1;i<=m;i++){
69 int l,r;
70 scanf("%d%d",&l,&r);
71 int ans=query(l,Root[r]);
72 printf("%d\n",ans);
73 }
74 return 0;
75 }