-
题目链接：
-
思路：
首先我是没读懂题目的，浏览了讨论区的dalao发现才知道就是求区间众数的出现次数。
然后肯定是用莫队，具体怎么写莫队其他题解都写得很详细，这里不赘述.然后观察数据范围1e9肯定要离散化。
但是题解里讲离散化的不多，我就讲一讲我自己瞎搞的一个离散化方法
看到题解里其他dalao都是什么lower_bound或我看不懂的神仙操作。而蒟蒻我就瞎搞出了一个比较暴力的,也通俗易懂方法---开了两个map.
第一个map al用来离散化，记录元素是否出现过.
第二个map getrk顾名思义，用来离散化获取每个数的排名.
dat[]用来记录原字符串,num[]用来记录去重后的数，即所有出现的元素
读入字符串后将num[]从大到小排序，记录每一个出现元素的排名，当然就是用getrk
接着就不管num[]，我们遍历一遍获取原字符串中每个数的排名完成离散化.
由于开了map,常数比较大，开了O2跑了2000多ms，但是能过就行了
-
代码：
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <map>
#include <cmath>
using namespace std;
const int maxn=200005;
map <int,bool>al;
map <int,int>getrk;
struct Ask{
int l,r,id,x;
}ask[maxn];
int num[maxn],dat[maxn],rk[maxn];
int belong[maxn],block;
int N,n=0,m;
int a[maxn],cnt[maxn];
int ans[maxn],anss=0;
template<class T>inline void read(T &x){
x=0;int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return ;
}
inline bool cmp0(const int&x,const int&y){
return x>y;
}
inline bool cmp2(const Ask &x,const Ask &y){
return belong[x.l]^belong[y.l]?belong[x.l]<belong[y.l]:belong[x.l]&1?x.r<y.r:x.r>y.r;
}
inline void init()
{
int x;
read(N),read(m);
block=N/sqrt(m*2/3);
n=0;
for(register int i=1;i<=N;i++){//N是原字符串长度
read(x);
dat[i]=x;
if(al[x]==0){//去重
num[++n]=x;//n是去重后num[]数组长度
al[x]=1;
}
belong[i]=(i-1)/block+1;
}
sort(num+1,num+1+n,cmp0);
for(register int i=1;i<=n;i++){
getrk[num[i]]=i;
// belong[i]=(i-1)/block+1;
}
for(register int i=1;i<=N;i++){
rk[i]=getrk[dat[i]];
}
//sort(num+1,num+1+n,cmp1);
for(register int i=1;i<=m;i++){
read(ask[i].l),read(ask[i].r);
ask[i].id=i;
}
sort(ask+1,ask+1+m,cmp2);
return;
}
inline void add(int x){
int now=rk[x];
if(anss==a[now])anss++;
cnt[a[now]]--;
a[now]++;
cnt[a[now]]++;
return;
}
inline void sub(int x){
int now=rk[x];
if(anss==a[now]&&cnt[a[now]]==1)anss--;
cnt[a[now]]--;
a[now]--;
cnt[a[now]]++;
return;
}
inline void solve()
{
int l=1,r=0,ll,rr;
cnt[0]=n;
for(register int i=1;i<=m;i++){
ll=ask[i].l,rr=ask[i].r;
while(r<rr)add(++r);
while(r>rr)sub(r),r--;
while(l<ll)sub(l),l++;
while(l>ll)add(--l);
ans[ask[i].id]=anss;
}
for(register int i=1;i<=m;i++){
printf("-%d
",ans[i]);
}
return ;
}
int main()
{
init();
solve();
return 0;
}