# 3339: Rmq Problem

## Sample Input

7 5 0 2 1 0 1 3 2 1 3 2 3 1 4 3 6 2 7

3 0 3 2 4

## Source

By X

``` 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;
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;
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;
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 }
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     {
60             dele(ll);
62             dele(rr);
66     }
67     for(int i=1;i<=q;i++)
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);
78     base=sqrt(n);
79     for(int i=1;i<=n;i++)
81     for(int i=1;i<=q;i++)
82     {
85     }
87     modui();
88     return 0;
89 }```
``` 1 #include<bits/stdc++.h>
2 using namespace std;
3 const int maxn = 1000005;
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);
40     int sz =ceil(sqrt(1.0*n));
41     for(int i=1;i<=n;i++)
42     {
44         pos[i]=(i-1)/sz;
45     }
46     for(int i=1;i<=m;i++)
47     {
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 }```

1811 篇文章114 人订阅

0 条评论

## 相关文章

2734

### FunDA（7）－ Reactive Streams to fs2 Pull Streams

Reactive-Stream不只是简单的push-model-stream, 它还带有“拖式”（pull-model）性质。这是因为在Iteratee...

1839

924

### 题型分析

1、 简单让A、B的值交换 a,b = 1,2 print(a,b) a = 1 b = 2 a,b = b,a print(a,b) a,b=[1,2],[5...

35410

33310

1013

641

2947

### C#系列之String和StringBuilder

首先和博园的各位打声招呼，小弟在博园呆了也有一年多了。平常一有时间就会过来看看文章，学习各位的经验，现在养成了一种一天不来博园，心里就不踏实的习惯，...

1104

### Javascript即将迎来Optional Chaining

Optional Chaining 现在处于 Stage 1。 它是什么？ Optional Chaining 使我们能检查一个对象上面是否存在某属性。其它一些...

3615