3339: Rmq Problem

Description

Input

Output

Sample Input

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

Sample Output

3 0 3 2 4

HINT

Source

By X

裸地莫队题目,

每次加入一个数,如果当前答案等于加入的数,就暴力向上加

每次删除一个数,如果删除的那个数比当前的答案小,那么当前的答案就赋值程这个数

因此

add和dele函数都非常好些。

但是,,,,,

我写的莫队各种RE,WA,TLE,MLE。。。。。。。。。。。。

和标称拍了一头午也没拍出错误来。。。。

也是醉了。。。

 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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏jessetalks

背后的故事之 - 快乐的Lambda表达式(二)

快乐的Lambda表达式   上一篇 背后的故事之 - 快乐的Lambda表达式(一)我们由浅入深的分析了一下Lambda表达式。知道了它和委托以及普通方法的区...

2734
来自专栏函数式编程语言及工具

FunDA(7)- Reactive Streams to fs2 Pull Streams

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

1839
来自专栏我杨某人的青春满是悔恨

深入理解 weak-strong dance

这时handler持有 Block 对象,而 Block 对象虽然捕获了weakSelf,延长了weakSelf这个局部变量的生命周期,但weakSelf是附有...

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
来自专栏IT笔记

2016头条校招笔试题(LRU)算法之JAVA实现

操作系统中可以使用LRU(Least Recently Used)内存淘汰旧数据的策略,如果内存需要加载新数据但空间不足,则会按照最近访问时间进行排序,并将最老...

33310
来自专栏我杨某人的青春满是悔恨

Monad 定律

monad 是支持>>=操作的 applicative 函子,>>=读作绑定,它的类型是:

1013
来自专栏恰同学骚年

数据结构基础温故-1.线性表(上)

开篇:线性表是最简单也是在编程当中使用最多的一种数据结构。例如,英文字母表(A,B,C,D...,Z)就是一个线性表,表中的每一个英文字母都是一个数据元素;又如...

641
来自专栏华仔的技术笔记

再议Block

2947
来自专栏.NET技术

C#系列之String和StringBuilder

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

1104
来自专栏前端黑板报

Javascript即将迎来Optional Chaining

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

3615

扫码关注云+社区