分块WA40求助

P2801 教主的魔法

_TLEer_的小号 @ 2021-03-06 09:35:51

Rt. Code:

#include<iostream>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,m,k,a[1000010],l,r,pos[1000010],cg[1000010],b[1000010];
char size;
int BLOCKSIZE;
struct BLOCK_T{
    int le,rt,tag;
    int binary_cut(int k){
        return BLOCKSIZE-(lower_bound(b+le,b+rt+1,k-tag)-(b+le));
    }
}block[10010];
int at_block_return(int now){
    return pos[now];
}
bool at_the_same_block(int x,int y){
    return at_block_return(x)==at_block_return(y);
}
void cgblock(int l,int r){
    for(int i=l;i<=r;i++)b[i]=a[i];
    sort(b+l,b+r+1);
}
void addblock(){
    BLOCKSIZE=sqrt(n);
    int blocktot=0;
    for(int i=0;i<n;i++){
        pos[i]=blocktot;
        b[i]=a[i];
        if(i>=(blocktot+1)*BLOCKSIZE-1){
            block[blocktot].le=blocktot*BLOCKSIZE;
            block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
            // system("pause");
            blocktot++;
            cgblock(block[blocktot].le,block[blocktot].rt);
        }
    }
    block[blocktot].le=blocktot*BLOCKSIZE;
    block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
    cgblock(block[blocktot].le,block[blocktot].rt);
//  cout<<blocktot<<' '<<block[blocktot].le<<' '<<block[blocktot].rt<<endl;
}
void add(int le,int rt,int k){
    if(at_the_same_block(le,rt)){
        for(int i=le;i<=rt;i++)
            a[i]+=k;
        cgblock(block[at_block_return(rt)].le,block[at_block_return(rt)].rt);
        return;
    }
    int lblock=at_block_return(le),rblock=at_block_return(rt);
    add(le,block[lblock].rt,k);
    add(block[rblock].le,rt,k);
    lblock++;rblock--;
    for(int i=lblock;i<=rblock;i++)
        block[i].tag+=k;
}
int ask(int le,int rt,int k){
    int ans=0;
//  cout<<le<<' '<<rt<<' '<<at_the_same_block(le,rt)<<endl;
    if(at_the_same_block(le,rt)){
        for(int i=le;i<=rt;i++)
            if(a[i]+block[at_block_return(rt)].tag>=k)
                ans++;
        return ans;
    }
    int lblock=at_block_return(le),rblock=at_block_return(rt);
    ans+=ask(le,block[lblock].rt,k)+ask(block[rblock].le,rt,k);
    lblock++;rblock--;
    for(int i=lblock;i<=rblock;i++)
        ans+=block[i].binary_cut(k);
    return ans;
}
signed main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    addblock();
    for(int i=0;i<m;i++){
        cin>>size>>l>>r>>k;
        l--,r--;
        if(size=='M'){
            add(l,r,k);
        }
        else{
            cout<<ask(l,r,k)<<endl;
        }
    }
    return 0;
}

|