首页 > 代码库 > 洛谷 P3709 大爷的字符串题
洛谷 P3709 大爷的字符串题
https://www.luogu.org/problem/show?pid=3709
题目背景
在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做，所以也出了一个字符串题：
题目描述
给你一个字符串a，每次询问一段区间的贡献
贡献定义：
每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S
如果S为空，你rp减1
如果S中有一个元素不小于x，则你rp减1，清空S
之后将x插入S
由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp初始为0
询问之间不互相影响~
输入输出格式
输入格式：
第一行两个数n，m，表示字符串长度与询问次数
之后一行n个数，表示字符串
由于你是大爷，所以字符集1e9
之后m行每行两个数，表示询问的左右区间
输出格式：
m行，每行一个数表示答案
输入输出样例
输入样例#1：
3 33 3 33 33 33 3
输出样例#1：
-1-1-1
说明
前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分，也可以进队了
提议：区间内出现次数最多的数出现了多少次
莫队
维护每个数的出现次数，出现次数为几的有几个数
注意cnt[0]的初值
#include<cmath>#include<cstdio>#include<algorithm>using namespace std;#define N 400001int n,m,k,siz;int key[N],hashh[N],sum[N],cnt[N],bl[N];int ans[N],tmp;struct node{ int l,r,id; bool operator < (node p)const { if(bl[l]!=bl[p.l]) return bl[l]<bl[p.l]; return r<p.r; } }e[N];inline int read(int &x){ x=0; char c=getchar(); while(c<‘0‘||c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); }}inline void update(int pos,bool w){ if(w) { cnt[sum[hashh[pos]]]--; sum[hashh[pos]]++; if(sum[hashh[pos]]==tmp+1) tmp++; cnt[sum[hashh[pos]]]++; } else { cnt[sum[hashh[pos]]]--; sum[hashh[pos]]--; cnt[sum[hashh[pos]]]++; while(!cnt[tmp]) tmp--; }}int main(){ read(n); read(m); siz=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i-1)/siz+1; for(int i=1;i<=n;i++) read(key[i]),hashh[i]=key[i]; sort(key+1,key+n+1); key[0]=unique(key+1,key+n+1)-(key+1); for(int i=1;i<=n;i++) hashh[i]=lower_bound(key+1,key+key[0]+1,hashh[i])-key; int u,v; for(int i=1;i<=m;i++) { read(u); read(v); e[i].l=u; e[i].r=v; e[i].id=i; if(e[i].l>e[i].r) swap(e[i].l,e[i].r); } sort(e+1,e+m+1); int L=1,R=0; cnt[0]=key[0]; for(int i=1;i<=m;i++) { while(L>e[i].l) update(--L,true); while(L<e[i].l) update(L++,false); while(R>e[i].r) update(R--,false); while(R<e[i].r) update(++R,true); ans[e[i].id]=-tmp; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}
洛谷 P3709 大爷的字符串题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。