3339: Rmq Problem

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 const int MAXN=3000011;
 9 /*inline void read(int &n)
10 {
11     char c='+';int x=0;bool flag=0;
12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
13     while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
14     n=flag==1?-x:x;
15 }*/
16 const int BUF=30000010;
17 char Buf[BUF],*buf=Buf;int BUFflag; 
18 inline void read(int &now)
19 {
20     for(now=0; ! isdigit (*buf); ++buf);
21     for(; isdigit ( *buf );now = now * 10+ (*buf-'0') ,++buf);
22 }
23 struct node
24 {
25     int l,r,bh,ans;
26 }ask[MAXN];
27 int n,q;
28 int a[MAXN];
29 int pos[MAXN];
30 int base;
31 inline int comp(const node &a,const node &b)
32 {
33     if(pos[a.l]==pos[a.l])     return pos[a.r]<pos[b.r];
34     else     return pos[a.l]<pos[b.l];
35 }
36 int happen[MAXN];
37 int out[MAXN];
38 int now=0;
39 inline void dele(int p)
40 {
41     happen[a[p]]--;
42     if(happen[a[p]]==0&&a[p]<now)
43         now=a[p];
44 }
45 inline void add(int p)
46 {
47     happen[a[p]]++;
48     if(now==a[p])
49     while(happen[now])
50         now++;
51 }
52 int modui()
53 {
54     int ll=1,rr=0;
55     for(int i=1;i<=q;i++)
56     {
57         for(;ask[i].l<ll;ll--)
58             add(ll-1);
59         for(;ask[i].l>ll;ll++)
60             dele(ll);
61         for(;ask[i].r<rr;rr--)
62             dele(rr);
63         for(;ask[i].r>rr;rr++)
64             add(rr+1);
65         ask[i].ans=now;
66     }
67     for(int i=1;i<=q;i++)
68         out[ask[i].bh]=ask[i].ans;
69     for(int i=1;i<=q;i++)
70         printf("%d\n",out[i]);
71 }
72 int main()
73 {
74     //freopen("a.in","r",stdin);
75 //    freopen("b.out","w",stdout);
76     fread(buf,1,BUF,stdin);
77     read(n);read(q);
78     base=sqrt(n);
79     for(int i=1;i<=n;i++)
80         read(a[i]),pos[i]=(i-1)/base+1;
81     for(int i=1;i<=q;i++)
82     {
83         int ll,rr;read(ll);read(rr);
84         ask[i].l=ll;ask[i].r=rr;ask[i].bh=i;
85     }
86     sort(ask+1,ask+q+1,comp);
87     modui();
88     return 0;
89 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000005;
 4 inline int read()
 5 {
 6     int x=0,f=1;char ch=getchar();
 7     while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
 8     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 9     return x*f;
10 }
11 int a[maxn],pos[maxn],c[maxn],Ans[maxn];
12 int ans,n,m;
13 struct query
14 {
15     int l,r,id;
16 }Q[maxn];
17 bool cmp(query a,query b)
18 {
19     if(pos[a.l]==pos[b.l])
20         return a.r<b.r;
21     return pos[a.l]<pos[b.l];
22 }
23 void Update(int x)
24 {
25     c[x]++;
26     if(ans==x)
27         while(c[ans])
28             ans++;
29 }
30 void Delete(int x)
31 {
32     c[x]--;
33     if(c[x]==0&&x<ans)ans=x;
34 }
35 int main()
36 {
37     freopen("a.in","r",stdin);
38     freopen("c.out","w",stdout);
39     n=read(),m=read();
40     int sz =ceil(sqrt(1.0*n));
41     for(int i=1;i<=n;i++)
42     {
43         a[i]=read();
44         pos[i]=(i-1)/sz;
45     }
46     for(int i=1;i<=m;i++)
47     {
48         Q[i].l=read();
49         Q[i].r=read();
50         Q[i].id = i;
51     }
52     sort(Q+1,Q+1+m,cmp);
53     int L=1,R=0;ans=0;
54     for(int i=1;i<=m;i++)
55     {
56         int id = Q[i].id;
57         while(R<Q[i].r)R++,Update(a[R]);
58         while(L>Q[i].l)L--,Update(a[L]);
59         while(R>Q[i].r)Delete(a[R]),R--;
60         while(L<Q[i].l)Delete(a[L]),L++;
61         Ans[id]=ans;
62     }
63     for(int i=1;i<=m;i++)
64         printf("%d\n",Ans[i]);
65 }