ZXCVB123 @ 2019-08-25 16:55:08
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,q,a[1010],l[1010],r[N],add[1010],belong[N],h[N];
bool order[1010];
int read(){
int we=0,w=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch)){
we=(we<<3)+(we<<1)+ch-'0';
ch=getchar();
}
return we*w;
}
void build(){
int size,num;
size=num=sqrt(n);
if(n%size) num++;
for(int i=1;i<=num;i++){
l[i]=r[i-1]+1;
r[i]=size*i;
if(i==num) r[i]=n;
for(int j=l[i];j<=r[i];j++)
belong[j]=i;
}
}
void inc(int ll,int rr,int x){
if(belong[ll]==belong[rr]){
for(int i=ll;i<=rr;i++)
a[i]+=x;
return;
}
for(int i=belong[ll]+1; i<=belong[rr]-1; i++) add[i]+=x;
for(int i=ll; i<=r[belong[ll]]; i++) a[i]+=x;
for(int i=l[belong[rr]]; i<=rr; i++) a[i]+=x;
if(ll!=l[belong[ll]]) order[belong[ll]]=0;
return;
}
inline int ask(int x,int y){
if(!order[x]){
sort(h+l[x],h+r[x]+1);
order[x]=1;
}
int k=lower_bound(h+l[x],h+r[x]+1,y-add[x])-h;
return r[x]-k+1;
}
inline int que(int x,int y,int z){
int ans=0;
if(belong[x]==belong[y]){
for(int i=x;i<=y;i++)
if(h[i]+add[belong[i]]>=z)
ans++;
return ans;
}
for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=ask(i,z);
for(int i=x;i<=r[belong[x]];i++)
if(h[i]+add[belong[i]]>=z){
ans++;
}
for(int i=l[belong[y]];i<=y;i++)
if(h[i]+add[belong[i]]>=z)
ans++;
return ans;
}
int main(){
n=read(); q=read();
for(int i=1;i<=n;i++)
a[i]=read();
build();
for(int i=1;i<=q;i++){
char ch;
cin>>ch;
int x=read(),y=read(),z=read();
if(ch=='M') inc(x,y,z);
else printf("%d\n",que(x,y,z));
}
return 0;
}
调了一下午了....
by yeaDonaby @ 2019-08-25 16:59:57
正解分块(逃
by 树套树 @ 2019-08-25 17:05:26
@OiNksEduCn 虽然我不会分块,但上面的应该就是分块吧。。。