题解 JSOI2011 棒棒糖

题解 JSOI2011 棒棒糖

题面

BZOJ

个人体会

自己切的一道题!

虽然和标程不一样但还是切了.

而且还是1A..

不过这题本来也就不难…

解析

一眼莫队

看到好多写主席树的,但想先用莫队试一下.

结果就过了…

用set套pair,每次找到最大值与区间长度/2比一下就行了…

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <set>
#include <algorithm>
#include <cmath>
#define mp make_pair
#define ll long long
#define filein(a) freopen(a".cpp","r",stdin)
#define fileout(a) freopen(a".cpp","w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=100005;
struct ques{int l,r,id;}q[N];
int n,m,a[N],c[N];
int gap,bl[N],ans[N];
multiset<pair<int,int> > s;
multiset<pair<int,int> >::iterator it;

inline bool cmp(ques a,ques b){
return bl[a.l]==bl[b.l]? a.r<b.r:a.l<b.l;
}

inline void add(int x){
it=s.find(mp(c[a[x]],a[x]));
if(it!=s.end()) s.erase(it);
c[a[x]]++;
s.insert(mp(c[a[x]],a[x]));
}

inline void del(int x){
it=s.find(mp(c[a[x]],a[x]));
if(it!=s.end()) s.erase(it);
c[a[x]]--;
s.insert(mp(c[a[x]],a[x]));
}

int main(){
n=read();m=read();
gap=sqrt(n);
for(int i=1;i<=n;i++) bl[i]=(i-1)/gap+1;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) q[i].l=read(),q[i].r=read();
for(int i=1;i<=m;i++) q[i].id=i;
sort(q+1,q+m+1,cmp);
int ql=1,qr=0;
for(int i=1;i<=m;i++){
int l=q[i].l,r=q[i].r;
while(ql<l) del(ql++);
while(ql>l) add(--ql);
while(qr<r) add(++qr);
while(qr>r) del(qr--);
it=s.end();it--;
pair<int,int> op=*it;
ans[q[i].id]=op.first>((r-l+1)/2)? op.second:0;
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
本文链接:<%= post.title %>
作者: Hastin
出处: http://zsq259.github.io/
本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名 Hastin及链接。
感谢您又打赏