首页 > 代码库 > P3709 大爷的字符串题（50分）
P3709 大爷的字符串题（50分）
题目背景
在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做，所以也出了一个字符串题：
题目描述
给你一个字符串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分，也可以进队了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<cstdlib> 6 #include<algorithm> 7 #include<vector> 8 #define hh 10 9 using namespace std; 10 const int MAXN=2000001; 11 void read(int & n) 12 { 13 char c=‘+‘;int x=0;bool flag=0; 14 while(c<‘0‘||c>‘9‘) 15 {c=getchar();if(c==‘-‘)flag=1;} 16 while(c>=‘0‘&&c<=‘9‘) 17 {x=x*10+(c-48);c=getchar();} 18 flag==1?n=-x:n=x; 19 } 20 int n,m; 21 int pos[MAXN]; 22 int base; 23 int rp=0; 24 struct node 25 { 26 int l,r,id; 27 }q[MAXN]; 28 struct dr 29 { 30 int a,p; 31 }a[MAXN]; 32 int comp(const node & a,const node &b) 33 { 34 if(pos[a.l]==pos[b.l]) 35 return a.r<b.r; 36 else 37 return pos[a.l]<pos[b.l]; 38 } 39 int cop(const dr &a,const dr &b) 40 { 41 return (a.a<b.a)||(a.a==b.a&&a.p<b.p); 42 } 43 int happen[MAXN];// 记录i出现了多少次 44 int cnt[MAXN];// 记录出现次数为j的有多少 45 int out[MAXN]; 46 void dele(int p) 47 { 48 if(rp==happen[p]&&cnt[happen[p]+hh]==1) 49 rp--; 50 cnt[happen[p]+hh]--; 51 cnt[happen[p]+hh-1]++; 52 happen[p]--; 53 } 54 void add(int p) 55 { 56 if(rp==happen[p]) 57 rp++; 58 cnt[happen[p]+hh]--; 59 cnt[happen[p]+hh+1]++; 60 happen[p]++; 61 } 62 int ls[MAXN]; 63 void modui() 64 { 65 int ll=1,rr=0; 66 for(int i=1;i<=m;i++) 67 { 68 for(;ll<q[i].l;ll++) 69 dele(ls[ll]); 70 for(;ll>q[i].l;ll--) 71 add(ls[ll-1]); 72 for(;rr>q[i].r;rr--) 73 dele(ls[rr]); 74 for(;rr<q[i].r;rr++) 75 add(ls[rr+1]); 76 out[q[i].id]=-rp; 77 } 78 for(int i=1;i<=m;i++) 79 printf("%d\n",out[i]); 80 } 81 int main() 82 { 83 read(n);read(m); 84 base=sqrt(n); 85 for(int i=1;i<=n;i++) 86 read(a[i].a),a[i].p=i; 87 sort(a+1,a+n+1,cop); 88 int j; 89 for(int i=1,j=0;i<=n;i++) 90 { 91 if (i==1||a[i].a!=a[i-1].a) j++; 92 ls[a[i].p]=j; 93 } 94 //for(int i=1;i<=n;i++) 95 // pos[i]=(i-1)/base+1; 96 int sqt=0; 97 for ( sqt=1; sqt*sqt<=n; sqt++); 98 99 for (int i=1; i<=n; i++) pos[i]=i/sqt;100 101 cnt[0]=j;102 for(int i=1;i<=m;i++)103 {104 read(q[i].l);105 read(q[i].r);106 q[i].id=i;107 }108 sort(q+1,q+m+1,comp);109 modui();110 return 0;111 }
P3709 大爷的字符串题（50分）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。