求助,分块出现奇怪错误QWQ

P2801 教主的魔法

tongyf @ 2020-06-28 00:05:40

只有三十分

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,siz,a[1000005],lazy[1000005],d[1000005];
int get_block(int x){
    return (x-1)/siz+1;
}
int get_start(int x){
    return (x-1)*siz+1;
}
int get_end(int x){
    return min(n,x*siz);
}
void change(int l,int r,int k){
    int ll=get_block(l),rr=get_block(r);
    if(ll==rr){
        for(int i=l;i<=r;i++) a[i]+=k;
        for(int i=get_start(ll);i<=get_end(ll);i++) d[i]=a[i];
        sort(d+get_start(ll),d+1+get_end(ll));
        return; 
    }
    for(int i=l;i<=get_end(ll);i++){
        a[i]+=k;
    }
    for(int i=get_start(ll);i<=get_end(ll);i++){
        d[i]=a[i];
    }
    sort(d+get_start(ll),d+1+get_end(ll));
    for(int i=get_start(rr);i<=r;i++){
        a[i]+=k;
    }
    for(int i=get_start(rr);i<=get_end(rr);i++){
        d[i]=a[i];
    }
    sort(d+get_start(rr),d+1+get_end(rr));
    for(int i=ll+1;i<=rr-1;i++) lazy[i]+=k;
}
int query(int l,int r,int k){
    int ans=0;
    int ll=get_block(l),rr=get_block(r);
    if(ll==rr){
        for(int i=l;i<=r;i++){
            if(lazy[ll]+a[i]>=k) ans++;
        }
        return ans; 
    }
    for(int i=l;i<=get_end(ll);i++) if(lazy[ll]+a[i]>=k) ans++;
    for(int i=get_start(rr);i<=r;i++) if(lazy[rr]+a[i]>=k) ans++;
    for(int i=ll+1;i<=rr-1;i++){
        ans+=get_end(i)-(lower_bound(d+get_start(i),d+1+get_end(i),k-lazy[i])-d)+1;
    }
    return ans;
}
signed main(){
    cin>>n>>q;
    siz=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i];
    }
    for(int i=1;i<=get_block(n);i++) sort(a+get_start(i),a+1+get_end(i));
    for(int i=1;i<=q;i++){
        char c;
        int aa,bb,cc;
        cin>>c>>aa>>bb>>cc;
        if(c=='A'){
            cout<<query(aa,bb,cc)<<endl;
        }
        else{
            change(aa,bb,cc);
        }
    }
    return 0;
}

by Caro23333 @ 2020-06-28 00:54:07

头像好评,溜了


by yu__xuan @ 2020-06-28 07:36:47

main函数里是给 a 排序吗?


by yu__xuan @ 2020-06-28 07:38:14

改成给 d 排序 T 了一个点


by yu__xuan @ 2020-06-28 07:38:20

@tongyf


by yu__xuan @ 2020-06-28 07:45:41

头像好评


by tongyf @ 2020-06-28 07:52:35

@yu__xuan 至少能过样例了


by tongyf @ 2020-06-28 07:53:14

T的点吸氧就可以过了


|