[bzoj3339]Rmq Problem

【题目描述】

【输入格式】

【输出格式】

【样例输入】

7 5

0 2 1 0 1 3 2

1 3

2 3

1 4

3 6

2 7

【样例输出】

【样例解释与数据范围】

什么都别说，先把暴力30分打出来

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 
 6 int n,q;
 7 int A[200001];
 8 bool F[200001];
 9 
10 int main()
11 {
12     scanf("%d %d",&n,&q);
13     for(int i=1;i<=n;i++)
14         scanf("%d",&A[i]);
15     for(int i=1;i<=q;i++)
16     {
17         int l,r;
18         memset(F,0,sizeof(F));
19         cin>>l>>r;
20         for(int j=l;j<=r;j++)
21             F[A[j]]=1;
22         for(int j=0;j<=200000;j++)
23             if(!F[j])
24             {
25                 cout<<j<<endl;
26                 break;
27             }
28     }
29     return 0;
30 }

线段树：

用mn[i]表示1~i的最小mex值

每当now<q[i].l时，更新now~next[now]-1节点的最小mex值

ask查询函数查到最右端的值即为left~right的最小mex值

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 using namespace std;
  5 
  6 const int INF=0x7fffffff;
  7 const int MAXN=200001;
  8 
  9 inline int read()
 10 {
 11     int x=0;char ch=getchar();
 12     while(ch<'0'||ch>'9')ch=getchar();
 13     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 14     return x;
 15 }
 16 
 17 struct Tree
 18 {
 19     int l,r,id;
 20 }q[MAXN];
 21 
 22 int n,m,k=0;
 23 int a[MAXN],sg[MAXN],next[MAXN],last[MAXN],ans[MAXN];
 24 int ls[MAXN*3],rs[MAXN*3],mn[MAXN*3];
 25 bool mark[MAXN];
 26 
 27 bool cmp(Tree a,Tree b)
 28 {
 29     return a.l<b.l;
 30 }
 31 
 32 void build(int node,int left,int right)//建立区间二叉树
 33 {
 34     ls[node]=left;rs[node]=right;mn[node]=INF;
 35     if(left==right){mn[node]=sg[left];return;}
 36     int mid=(left+right)>>1;
 37     build(node<<1,left,mid);
 38     build(node<<1|1,mid+1,right);
 39 }
 40 
 41 void pushdown(int k)//更新节点mex最小值
 42 {
 43     int l=ls[k],r=rs[k];
 44     if(l==r)return;
 45     mn[k<<1]=min(mn[k],mn[k<<1]);
 46     mn[k<<1|1]=min(mn[k],mn[k<<1|1]);
 47 }
 48 
 49 int ask(int k,int x)//查询mex
 50 {
 51     if(mn[k]!=INF)pushdown(k);
 52     int l=ls[k],r=rs[k];
 53     if(l==r)return mn[k];
 54     int mid=(l+r)>>1;
 55     if(x<=mid) return ask(k<<1,x);
 56     return ask(k<<1|1,x);
 57 }
 58 
 59 void update(int k,int x,int y,int val)//更新二叉树
 60 {
 61     if(mn[k]!=INF) pushdown(k);
 62     int l=ls[k],r=rs[k];
 63     if(l==x&&y==r){mn[k]=min(mn[k],val);return;}
 64     int mid=(l+r)>>1;
 65     if(y<=mid) update(k<<1,x,y,val);
 66     else if(x>mid) update(k<<1|1,x,y,val);
 67     else
 68     {
 69         update(k<<1,x,mid,val);
 70         update(k<<1|1,mid+1,y,val);
 71     }
 72 }
 73 
 74 int main()
 75 {
 76     //freopen("mex.txt","w",stdout);
 77     n=read();m=read();
 78     for(int i=1;i<=n;i++)
 79     {
 80         a[i]=read();
 81         mark[a[i]]=1;
 82         if(a[i]==k)
 83             while(mark[k])k++;
 84         sg[i]=k;
 85     }
 86     build(1,1,n);
 87     for(int i=n;i>0;i--)
 88         next[i]=last[a[i]],last[a[i]]=i;//记录上一个a[i]出现的位置
 89     for(int i=1;i<=m;i++)
 90     {
 91         q[i].id=i;
 92         q[i].l=read();
 93         q[i].r=read();
 94     }
 95     sort(q+1,q+m+1,cmp);
 96     int now=1;
 97     for(int i=1;i<=m;i++)
 98     {
 99         while(now<q[i].l)
100         {
101             if(!next[now])next[now]=n+1;
102             update(1,now,next[now]-1,a[now]);
103             now++;
104         }
105         ans[q[i].id]=ask(1,q[i].r);
106     }
107     for(int i=1;i<=m;i++)
108         printf("%d
",ans[i]);
109     return 0;
110 }

借鉴了一下黄学长的代码。。。第一次玩线段树（明明是第二次