BZOJ 3343: 教主的魔法

 

3343: 教主的魔法

题目连接：

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 }