steven张 @ 2017-09-24 21:30:10
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+7;
const int sqrtn=1e3+7;
int block,n,num,q;
int belong[maxn],l[sqrtn],r[sqrtn],a[maxn],b[maxn],add[sqrtn];
bool cmp(int x,int y){return x<y;}
void print()
{
for(int i=1;i<=num;i++)
{
for(int j=l[i];j<=r[i];j++)
{
printf("%d",b[j]);
}
printf("\n");
}
}
void build()
{
block=sqrt(n);
num=n/block;if(n%block)num++;
for(int i=1;i<=num;i++)
l[i]=(i-1)*block+1,r[i]=i*block;
r[num]=n;
for(int i=1;i<=n;i++)
belong[i]=(i-1)/block+1;
}
void reset(int x)
{
for(int i=l[x];i<=r[x];i++)
b[i]=a[i];
sort(b+l[x],b+r[x]+1,cmp);
}
void update(int le,int ri,int v)
{
if(belong[le]==belong[ri])
for(int i=le;i<=ri;i++)
a[i]+=v;
else
{
for(int i=le;i<=r[belong[le]];i++)
a[i]+=v;
for(int i=l[belong[ri]];i<=ri;i++)
a[i]+=v;
for(int i=belong[le]+1;i<=belong[ri]-1;i++)
add[i]+=v;
for(int i=1;i<=num;i++)reset(i);
}
}
int find(int x,int v)
{
int le=l[belong[x]],ri=r[belong[ri]];
while(le<=ri)
{
int m=(le+ri)>>1;
if(b[m]>v) ri=m-1;
else le=m+1;
}
// printf("%d",r[belong[ri]]-le+1);
return r[belong[ri]]-le+1;
}
int query(int le,int ri,int v)
{
int ans=0;
if(belong[le]==belong[ri])
{
for(int i=le;i<=ri;i++)
if(a[i]+add[belong[i]]>=v) ans++;
}
else
{
for(int i=le;i<=r[belong[le]];i++)
if(a[i]+add[belong[i]]>=v) ans++;
for(int i=l[belong[ri]];i<=ri;i++)
if(a[i]+add[belong[i]]>=v) ans++;
for(int i=belong[le]+1;i<=belong[ri]-1;i++)
ans+=find(i,v-add[i]);
}
return ans;
}
int main()
{
scanf("%d%d",&n,&q);
build();
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=num;i++)reset(i);
for(int k=1;k<=q;k++)
{
char ch;
int t1,t2,t3;
scanf(" %c%d%d%d",&ch,&t1,&t2,&t3);
if(ch=='A')printf("%d\n",query(t1,t2,t3));
else
{
update(t1,t2,t3);
print();
}
}
}
/* 10 5 1 2 3 4 5 9 1 2 8 4
A 1 3 3
A 1 10 4
A 1 10 5
A 1 10 6
A 1 10 8
*/ 这里有一个非常诡异的事情就是,在find函数里加上一个输出,程序会崩,求大佬解答!