网上找的分块题解,不知道哪里错了,求解答

P2801 教主的魔法

steven张 @ 2017-09-24 21:30:10

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e6+7;
const int sqrtn=1e3+7;
int block,n,num,q;
int belong[maxn],l[sqrtn],r[sqrtn],a[maxn],b[maxn],add[sqrtn];
bool cmp(int x,int y){return x<y;}
void print()
{
    for(int i=1;i<=num;i++)
    {
        for(int j=l[i];j<=r[i];j++)
        {
            printf("%d",b[j]);
        }
        printf("\n");
    }
}
void build()
{
    block=sqrt(n);
    num=n/block;if(n%block)num++;
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
}
void reset(int x)
{
    for(int i=l[x];i<=r[x];i++)
        b[i]=a[i];
    sort(b+l[x],b+r[x]+1,cmp);
}
void update(int le,int ri,int v)
{
    if(belong[le]==belong[ri])
        for(int i=le;i<=ri;i++)
            a[i]+=v;
    else
    {
        for(int i=le;i<=r[belong[le]];i++)
            a[i]+=v;
        for(int i=l[belong[ri]];i<=ri;i++)
            a[i]+=v;
        for(int i=belong[le]+1;i<=belong[ri]-1;i++)
            add[i]+=v;
        for(int i=1;i<=num;i++)reset(i);
    }
}
int find(int x,int v)
{
    int le=l[belong[x]],ri=r[belong[ri]];
    while(le<=ri)
    {
        int m=(le+ri)>>1;
        if(b[m]>v) ri=m-1;
        else le=m+1;
    }
//    printf("%d",r[belong[ri]]-le+1);
    return r[belong[ri]]-le+1;
}
int query(int le,int ri,int v)
{
    int ans=0;
    if(belong[le]==belong[ri])
    {
        for(int i=le;i<=ri;i++)
            if(a[i]+add[belong[i]]>=v) ans++;
    }
    else
    {
        for(int i=le;i<=r[belong[le]];i++)
            if(a[i]+add[belong[i]]>=v) ans++;
        for(int i=l[belong[ri]];i<=ri;i++)
            if(a[i]+add[belong[i]]>=v) ans++;
        for(int i=belong[le]+1;i<=belong[ri]-1;i++)
            ans+=find(i,v-add[i]);
    }
    return ans;
}
int main()
{
    scanf("%d%d",&n,&q);
    build();
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=num;i++)reset(i);
    for(int k=1;k<=q;k++)
    {
        char ch;
        int t1,t2,t3;
        scanf(" %c%d%d%d",&ch,&t1,&t2,&t3);
        if(ch=='A')printf("%d\n",query(t1,t2,t3));
        else
        {
            update(t1,t2,t3);
            print();
        }
    }
}

/* 10 5 1 2 3 4 5 9 1 2 8 4

A 1 3 3

A 1 10 4

A 1 10 5

A 1 10 6

A 1 10 8

*/ 这里有一个非常诡异的事情就是,在find函数里加上一个输出,程序会崩,求大佬解答!


|