90pts TLE求调
查看原帖
90pts TLE求调
330124
JackyLu0520楼主2025/6/20 11:03

不知道是写假了还是常数大,我在本地跑#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;
}
2025/6/20 11:03
加载中...