东郭 @ 2020-07-29 08:17:33
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
int n,m,num,a[1000001],b[1000001],bel[1000001],l[10001],r[10001],flag[10001];
inline void change(int x){
for(int i=l[bel[x]];i<=r[bel[x]];i++)b[i]=a[i];
sort(b+l[bel[x]],b+r[bel[x]]+1);
return;
}
inline void update(int x,int y,int z){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++)a[i]+=z;
change(x);
return;
}
for(int i=x;i<=r[bel[x]];i++)a[i]+=z;
for(int i=l[bel[y]];i<=y;i++)a[i]+=z;
change(x);change(y);
for(int i=bel[x]+1;i<=bel[y]-1;i++)flag[i]+=z;
return;
}
inline int find(int x,int y,int z){
while(x<=y){
int mid=(x+y)>>1;
if(b[mid]<z) x=mid+1;
else y=mid-1;
}
return y;
}
inline int query(int x,int y,int z){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++)
if(a[i]+flag[bel[x]]>=z)
ans++;
return ans;
}
for(int i=x;i<=r[bel[x]];i++)
if(a[i]+flag[bel[x]]>=z)
ans++;
for(int i=l[bel[y]];i<=y;i++)
if(a[i]+flag[bel[y]]>=z)
ans++;
for(int i=bel[x]+1;i<=bel[y]-1;i++)
ans+=r[i]-find(l[i],r[i],z-flag[bel[i]])+1;
return ans;
}
int main(){
num=sqrt(n);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=num;i++) l[i]=r[i-1]+1,r[i]=i*num;
if(r[num]<n) num++,l[num]=r[num-1]+1,r[num]=n;
for(int i=1;i<=num;i++)
for(int j=l[i];j<=r[i];j++)
bel[j]=i,b[j]=a[j];
for(int i=1;i<=num;i++)
sort(b+l[i],b+r[i]+1);
char lon[3];
int x1,x2,x3;
while(m--){
cin>>lon;
scanf("%d%d%d",&x1,&x2,&x3);
if(lon[0]=='A') printf("%d\n",query(x1,x2,x3));
else update(x1,x2,x3);
}
return 0;
}
时间复杂度与题解一样,TLE了5,6,7,8,10五个点。
by string_error @ 2020-07-29 09:28:20
az