P3709 大爷的字符串题(50分)
2018-06-17 22:20:47来源:未知 阅读 ()
题目背景
在那遥远的西南有一所学校
/*被和谐部分*/
然后去参加该省省选虐场
然后某蒟蒻不会做,所以也出了一个字符串题:
题目描述
给你一个字符串a,每次询问一段区间的贡献
贡献定义:
每次从这个区间中随机拿出一个字符x,然后把x从这个区间中删除,你要维护一个集合S
如果S为空,你rp减1
如果S中有一个元素不小于x,则你rp减1,清空S
之后将x插入S
由于你是大爷,平时做过的题考试都会考到,所以每次询问你搞完这段区间的字符之后最多还有多少rp?rp初始为0
询问之间不互相影响~
输入输出格式
输入格式:
第一行两个数n,m,表示字符串长度与询问次数
之后一行n个数,表示字符串
由于你是大爷,所以字符集1e9
之后m行每行两个数,表示询问的左右区间
输出格式:
m行,每行一个数表示答案
输入输出样例
3 3 3 3 3 3 3 3 3 3 3
-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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:P1057 传球游戏
- Z 字形变换 2020-04-14
- 翻转字符串里面的单词 2020-04-10
- 用C++实现:FJ的字符串打印 2020-04-04
- [题记]字符串转换整数-leetcode 2020-04-03
- C++ 字符串输入 2020-03-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash