题目背景
在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做，所以也出了一个字符串题：
题目描述
给你一个字符串a，每次询问一段区间的贡献
贡献定义：
每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S
如果S为空，你rp减1
如果S中有一个元素不小于x，则你rp减1，清空S
之后将x插入S
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp初始为0
询问之间不互相影响~
输入输出格式
输入格式：
第一行两个数n，m，表示字符串长度与询问次数
之后一行n个数，表示字符串
由于你是大爷，所以字符集1e9
之后m行每行两个数，表示询问的左右区间
输出格式：
m行，每行一个数表示答案
输入输出样例
说明
前4个点1s，后面的点4s
对于10%的数据，是样例
对于另外10%的数据，n,m <= 100
对于另外10%的数据，n,m <= 1000
对于另外10%的数据，n,m <= 10000
对于另外10%的数据，n,m <= 100000
对于100%的数据，n,m <= 200000
保证数据向某省省选day1T2一样sb，大家尽情用暴力水过题吧！
没事，你只要在一个好学校，就算这题只能拿到10分，也可以进队了
题解
这明明是道语文题……
我是完全看不出为啥会变成让我们求区间众数的……
交上去T了两次发现自己根本没分块……就是俩指针在哪里瞎蹦……
总而言之题意就是让我们求区间众数的出现次数，然后再把答案取反
这种事情莫队轻松搞定
先离散，记录一下$x$出现次数$num[x]$和出现次数为$x$的数的个数$cnt[x]$
然后剩下的基本看代码
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 inline int read(){ 11 #define num ch-'0' 12 char ch;bool flag=0;int res; 13 while(!isdigit(ch=getc())) 14 (ch=='-')&&(flag=true); 15 for(res=num;isdigit(ch=getc());res=res*10+num); 16 (flag)&&(res=-res); 17 #undef num 18 return res; 19 } 20 char sr[1<<21],z[20];int C=-1,Z; 21 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} 22 inline void print(int x){ 23 if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x; 24 while(z[++Z]=x%10+48,x/=10); 25 while(sr[++C]=z[Z],--Z);sr[++C]=' '; 26 } 27 const int N=400005; 28 int cnt[N],num[N],a[N],b[N],ans[N],rt[N],ansn,l,r,n,m,k,s; 29 struct node{ 30 int l,r,id; 31 }q[N]; 32 inline bool cmp(node a,node b){ 33 return rt[a.l]==rt[b.l]?rt[a.l]&1?a.r<b.r:a.r>b.r:a.l<b.l; 34 } 35 inline void add(int x){ 36 if(num[x]==ansn) ++ansn; 37 --cnt[num[x]],++cnt[num[x]+1],++num[x]; 38 } 39 inline void del(int x){ 40 if(num[x]==ansn&&cnt[num[x]]==1) --ansn; 41 --cnt[num[x]],++cnt[num[x]-1],--num[x]; 42 } 43 int main(){ 44 //freopen("testdata.in","r",stdin); 45 k=n=read(),m=read(),s=sqrt(n); 46 for(int i=1;i<=n;++i) a[i]=b[i]=read(),rt[i]=(i-1)/s+1; 47 sort(b+1,b+1+n); 48 k=unique(b+1,b+1+n)-b-1; 49 for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+1+k,a[i])-b; 50 for(int i=1;i<=m;++i) 51 q[i].l=read(),q[i].r=read(),q[i].id=i; 52 sort(q+1,q+1+m,cmp); 53 l=1,r=0; 54 for(int i=1;i<=m;++i){ 55 while(l>q[i].l) add(a[--l]); 56 while(r<q[i].r) add(a[++r]); 57 while(l<q[i].l) del(a[l++]); 58 while(r>q[i].r) del(a[r--]); 59 ans[q[i].id]=-ansn; 60 } 61 for(int i=1;i<=m;++i) print(ans[i]); 62 Ot(); 63 return 0; 64 }