求助各位巨佬。(好人一生平安)【可怜】【可怜】

P2801 教主的魔法

xlxl @ 2019-07-17 11:34:05

#include<bits/stdc++.h>
using namespace std;
char tot;
long long u,v;
long long b[100010],a[100010],sum[100010],add[100010];
long long QMQ,gg,h,n,m,L[100010],R[100010],pos[100010];
void Blocking(long long x){
    long long l=(x-1)*h+1;
    long long r=min(x*h,n);
    for(long long i=l;i<=r;i++){
        b[i]=a[i];
    }
    sort(b+l,b+r+1);
}
void modify(long long x,long long y,long long d){
    if(pos[x]==pos[y]){
        for(long long i=x;i<=y;i++){
            a[i]+=d;
        }
    }
    else{
        for(long long i=x;i<=pos[x]*h;i++){
            a[i]+=d;
        }
        for(long long i=(pos[y]-1)*h+1;i<=y;i++){
            a[i]+=d;
        }
        for(long long i=pos[x]+1;i<=pos[y]-1;i++){
            add[i]+=d;
        }
    }
}
long long find(long long x,long long v){
    long long l=(x-1)*h+1;
    long long r=min(x*h,n);
    long long tmp=r;
    while(l<=r){
        long long mid=(l+r)/2;
        if(b[mid]<v)
            r=mid-1;
        else{
            l=mid+1;
        }
    }
    return tmp-l+1;
}
long long found(long long x,long long y,long long z){
    long long ans=0;
    if(pos[x]==pos[y]){
        for(long long i=x;i<=y;i++){
            if(a[i]+add[pos[i]]>=z){
                ans++;
            }
        }
    }
    for(long long i=x;i<=pos[x]*h;i++){
        if(a[i]+add[pos[i]]>=z){
            ans++;
        }
    }
    for(long long i=(pos[y]-1)*h+1;i<=y;i++){
        if(a[i]+add[pos[i]]>=z){
            ans++;
        }
    }
    for(long long i=pos[x]+1;i<=pos[y]-1;i++){
        ans+=find(i,z-add[i]);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    h=sqrt(n);
    for(long long i=1;i<=n;i++){
        cin>>a[i];
        pos[i]=(i-1)/h+1;
        b[i]=a[i];
    }
    gg=ceil(n/h);
    for(long long i=1;i<=gg;i++){
        Blocking(i);
    }
    for(long long i=1;i<=m;i++){
        cin>>tot>>u>>v>>QMQ;
        if(tot=='M'){
            modify(u,v,QMQ);
        }
        else{
            cout<<found(u,v,QMQ)<<endl;
        }
    }
    return 0;
}

|