同问 为什么第八个点不吸氧会T ?

P2801 教主的魔法

Explorelore @ 2019-10-07 23:46:03

#include<cstdio>
#include<vector>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 1000010
using namespace std;
ll read(){
    ll x=0,f=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int n,q,blo;
int a[N],atag[N],bl[N];
vector <int > v[N];
void reset(int x){
    v[x].clear();
     for(int i=(x-1)*blo+1;i<=x*blo;i++) v[x].push_back(a[i]);
    sort(v[x].begin(),v[x].end());
}
void add(int l,int r,int c){
    for(int i=l;i<=min(r,bl[l]*blo);i++) a[i]+=c;
    reset(bl[l]);
    if(bl[l]!=bl[r]){
        for(int i=(bl[r]-1)*blo+1;i<=r;i++) a[i]+=c;
        reset(bl[r]);
    }
    for(int i=bl[l]+1;i<=bl[r]-1;i++) atag[i]+=c;
}
void ask(int l,int r,int c){
    int sum=0;
    for(int i=l;i<=min(r,bl[l]*blo);i++) if(a[i]+atag[bl[i]]>=c) sum++;
    if(bl[l]!=bl[r]){
        for(int i=(bl[r]-1)*blo+1;i<=r;i++) if(a[i]+atag[bl[i]]>=c) sum++;
    }
    for(int i=bl[l]+1;i<=bl[r]-1;i++){
        int x=lower_bound(v[i].begin(),v[i].end(),c-atag[i])-v[i].begin();
        sum+=blo-x;
    }
    printf("%d\n",sum);
}
int main(){
    n=read(),q=read(),blo=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        bl[i]=(i-1)/blo+1;
        v[bl[i]].push_back(a[i]);
    }
    for(int i=1;i<=bl[n];i++) sort(v[i].begin(),v[i].end());
    for(int i=1;i<=q;i++){
        char opt; cin>>opt;
        int l=read(),r=read(),c=read();
        if(opt=='M') add(l,r,c);
        else ask(l,r,c);
    }   
    return 0;
}

|