不知道是写假了还是常数大,我在本地跑#10的数据一直是大约2.5s。
我已经卡不动了,求救
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+10,M=3010,SQRTN=1e3+10;;
int n,m,a[N],L[SQRTN],R[SQRTN],tag[SQRTN],bel[N],sorted[N];
inline void init(){
int sz=sqrt(n);
memcpy(sorted+1,a+1,n*sizeof(int));
for(int i=1;i<=(n+sz-1)/sz;i++){
L[i]=(i-1)*sz+1;R[i]=min(i*sz,n);
for(int j=L[i];j<=R[i];j++)
bel[j]=i;
tag[i]=0;
sort(sorted+L[i],sorted+R[i]+1);
}
}
inline void addbf(int p,int l,int r,int k){
for(int i=l;i<=r;i++)
a[i]+=k;
memcpy(sorted+L[p],a+L[p],(R[p]-L[p]+1)*sizeof(int));
sort(sorted+L[p],sorted+R[p]+1);
}
inline void add(int l,int r,int k){
int pl=bel[l],pr=bel[r];
if(pl==pr) addbf(pl,l,r,k);
else{
l==L[pl]?(void)(pl--):addbf(pl,l,R[pl],k);
r==R[pr]?(void)(pr++):addbf(pr,L[pr],r,k);
for(int i=pl+1;i<=pr-1;i++)
tag[i]+=k;
}
}
inline int querybf(int p,int l,int r,int k){
int ret=0;
for(int i=l;i<=r;i++)
if(a[i]+tag[p]>=k)
ret++;
return ret;
}
inline int query(int l,int r,int k){
int pl=bel[l],pr=bel[r];
if(pl==pr) return querybf(pl,l,r,k);
else{
int ret=0;
l==L[pl]?pl--:ret+=querybf(pl,l,R[pl],k);
r==R[pr]?pr++:ret+=querybf(pr,L[pr],r,k);
for(int i=pl+1;i<=pr-1;i++){
int p=lower_bound(sorted+L[i],sorted+R[i]+1,k-tag[i])-sorted;
ret+=R[i]-p+1;
}
return ret;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
while(m--){
char op;
scanf(" %c",&op);
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
if(op=='M') add(l,r,k);
else printf("%d\n",query(l,r,k));
}
return 0;
}