求助大佬,为什么爆零?

P2801 教主的魔法

ZXCVB123 @ 2019-08-25 16:55:08

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,q,a[1010],l[1010],r[N],add[1010],belong[N],h[N];
bool order[1010];
int read(){
    int we=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        we=(we<<3)+(we<<1)+ch-'0';
        ch=getchar();
    }
    return we*w;
}
void build(){
    int size,num;
    size=num=sqrt(n);
    if(n%size) num++;
    for(int i=1;i<=num;i++){
        l[i]=r[i-1]+1;
        r[i]=size*i;
        if(i==num) r[i]=n;
        for(int j=l[i];j<=r[i];j++)
            belong[j]=i;
    }
}
void inc(int ll,int rr,int x){
    if(belong[ll]==belong[rr]){
        for(int i=ll;i<=rr;i++)
            a[i]+=x;
        return;
    }
    for(int i=belong[ll]+1; i<=belong[rr]-1; i++) add[i]+=x;
    for(int i=ll; i<=r[belong[ll]]; i++) a[i]+=x;
    for(int i=l[belong[rr]]; i<=rr; i++) a[i]+=x;
    if(ll!=l[belong[ll]]) order[belong[ll]]=0;
    return;
}
inline int ask(int x,int y){
    if(!order[x]){
        sort(h+l[x],h+r[x]+1);
        order[x]=1;
    }
    int k=lower_bound(h+l[x],h+r[x]+1,y-add[x])-h;
    return r[x]-k+1;
}
inline int que(int x,int y,int z){
    int ans=0;
    if(belong[x]==belong[y]){
        for(int i=x;i<=y;i++)
            if(h[i]+add[belong[i]]>=z)
                ans++;
        return ans;
    }
    for(int i=belong[x]+1;i<=belong[y]-1;i++) ans+=ask(i,z);
    for(int i=x;i<=r[belong[x]];i++)
        if(h[i]+add[belong[i]]>=z){
            ans++;
        }
    for(int i=l[belong[y]];i<=y;i++)
        if(h[i]+add[belong[i]]>=z)
            ans++;
    return ans;
}
int main(){
    n=read(); q=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    build();
    for(int i=1;i<=q;i++){
        char ch;
        cin>>ch;
        int x=read(),y=read(),z=read();
        if(ch=='M') inc(x,y,z);
        else printf("%d\n",que(x,y,z));
    }
    return 0;
}

调了一下午了....


by yeaDonaby @ 2019-08-25 16:59:57

正解分块(逃


by 树套树 @ 2019-08-25 17:05:26

@OiNksEduCn 虽然我不会分块,但上面的应该就是分块吧。。。


|