BZOJ 3343: 教主的魔法
2018-06-17 21:00:14来源:未知 阅读 ()
题目连接:
http://www.lydsy.com/JudgeOnline/problem.php?id=3343
Description
教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。
每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)
CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。
WD巨懒,于是他把这个回答的任务交给了你。
Input
第1行为两个整数N、Q。Q为问题数与教主的施法数总和。
第2行有N个正整数,第i个数代表第i个英雄的身高。
第3到第Q+2行每行有一个操作:
(1) 若第一个字母为“M”,则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。
(2) 若第一个字母为“A”,则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。
Output
对每个“A”询问输出一行,仅含一个整数,表示闭区间 [L, R] 内身高大于等于C的英雄数。
Sample Input
5 3
1 2 3 4 5
A 1 5 4
M 3 5 1
A 1 5 4
Sample Output
2
3
Hint
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000000+5; 4 5 int block,num,l[maxn],r[maxn]; 6 int belong[maxn],n,m,a[maxn]; 7 int d[maxn],p[maxn]; 8 9 inline void bt() 10 { 11 block=sqrt(n); 12 num=n/block; 13 if(n%block) 14 num++; 15 for(int i=1;i<=num;i++) 16 l[i]=(i-1)*block+1,r[i]=i*block; 17 r[num]=n; 18 19 for(int i=1;i<=n;i++) 20 { 21 belong[i]=(i-1)/block+1; 22 d[i]=a[i]; 23 } 24 for(int i=1;i<=num;i++) 25 sort(d+l[i],d+r[i]+1); 26 } 27 28 inline void update(int ll,int rr,int w) 29 { 30 if(belong[ll]==belong[rr]) 31 { 32 for(int i=l[belong[ll]];i<=r[belong[rr]];i++) 33 { 34 a[i]+=p[belong[ll]]; 35 } 36 p[belong[ll]]=0; 37 for(int i=ll;i<=rr;i++) 38 a[i]+=w; 39 for(int i=l[belong[ll]];i<=r[belong[rr]];i++) 40 d[i]=a[i]; 41 sort(d+l[ll],d+r[rr]+1); 42 return ; 43 } 44 45 for(int i=l[belong[ll]];i<=r[belong[ll]];i++) 46 a[i]+=p[belong[ll]]; 47 p[belong[ll]]=0; 48 for(int i=ll;i<=r[belong[ll]];i++) 49 a[i]+=w; 50 for(int i=l[belong[ll]];i<=r[belong[ll]];i++) 51 d[i]=a[i]; 52 sort(d+l[belong[ll]],d+r[belong[ll]]+1); 53 54 for(int i=l[belong[rr]];i<=r[belong[rr]];i++) 55 a[i]+=p[belong[rr]]; 56 p[belong[rr]]=0; 57 for(int i=l[belong[rr]];i<=rr;i++) 58 a[i]+=w; 59 for(int i=l[belong[rr]];i<=r[belong[rr]];i++) 60 d[i]=a[i]; 61 sort(d+l[belong[rr]],d+r[belong[rr]]+1); 62 63 for(int i=belong[ll]+1;i<belong[rr];i++) 64 p[i]+=w; 65 } 66 67 inline int ask(int x,int y,int w) 68 { 69 int ans=0; 70 if(belong[x]==belong[y]) 71 { 72 for(int i=x;i<=y;i++) 73 if(a[i]+p[belong[i]]>=w) 74 ans++; 75 return ans; 76 } 77 for(int i=x;i<=r[belong[x]];i++) 78 if(a[i]+p[belong[i]]>=w) 79 ans++; 80 81 for(int i=l[belong[y]];i<=y;i++) 82 if(a[i]+p[belong[i]]>=w) 83 ans++; 84 85 for(int i=belong[x]+1;i<belong[y];i++) 86 { 87 int ll=l[i],rr=r[i],Ans=0; 88 while(ll<=rr) 89 { 90 int mid=(ll+rr)>>1; 91 if(d[mid]+p[i]>=w) 92 rr=mid-1,Ans=r[i]-mid+1; 93 else 94 ll=mid+1; 95 } 96 ans+=Ans; 97 } 98 return ans; 99 } 100 101 int main() 102 { 103 scanf("%d%d",&n,&m); 104 for(int i=1;i<=n;i++) 105 { 106 scanf("%d",&a[i]); 107 } 108 bt(); 109 for(int i=1;i<=m;i++) 110 { 111 char ch; 112 int l,r,w,c; 113 cin>>ch; 114 if(ch=='M') 115 { 116 scanf("%d%d%d",&l,&r,&w); 117 update(l,r,w); 118 } 119 else 120 { 121 scanf("%d%d%d",&l,&r,&c); 122 printf("%d\n",ask(l,r,c)); 123 } 124 } 125 return 0; 126 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:BZOJ 2002: [Hnoi2010]Bounce 弹飞绵羊
下一篇:内存对齐
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-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