LibreOJ 6280 . 数列分块入门 4

题目链接：https://loj.ac/problem/6280

加一个数组保存块的和。

代码：

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<set>

#include<cstdio>

#include<string>

#include<deque>

using namespace std;

typedef long long LL;

#define eps 1e-8

#define INF 0x3f3f3f3f

#define maxn 50010

/*struct point{

    int u,w;

};

bool operator <(const point &s1,const point &s2)

{

    if(s1.w!=s2.w)

    return s1.w>s2.w;

    else

    return s1.u>s2.u;

}*/

LL n,m,k,t,block;

LL a[maxn],sum[maxn],tag[maxn];

int lump[maxn];

void add(LL l,LL r,LL w)

{

    for(int i=l;i<=min(lump[l]*block,r);i++)//这里错了n次...这里是r表示n，是为了防止l和r在一个块里面的情况，要引以为戒

    {

        a[i]+=w;

        sum[lump[l]]+=w;

    }

    if(lump[l]!=lump[r])

    {

        for(int i=(lump[r]-)*block+;i<=r;i++)

        {

            a[i]+=w;

            sum[lump[r]]+=w;

        }

    }

    for(int i=lump[l]+;i<=lump[r]-;i++)

    {

        tag[i]+=w;

        sum[i]+=w*block;

    }

}

LL get_sum(LL l,LL r)

{

    LL ans=;

    for(int i=l;i<=min(lump[l]*block,r);i++)

    ans+=a[i]+tag[lump[l]];

    if(lump[l]!=lump[r])

    {

        for(int i=block*(lump[r]-)+;i<=r;i++)

        ans+=a[i]+tag[lump[r]];

    }

    for(int i=lump[l]+;i<=lump[r]-;i++)

    ans+=sum[i];

    return ans;

}

int main()

{

    scanf("%lld",&n);

    block=sqrt(n);

    fill(sum,sum+maxn-,);

    fill(tag,tag+maxn-,);

    for(int i=;i<=n;i++)

    {

        scanf("%lld",&a[i]);

        lump[i]=(i-)/block+;

        sum[lump[i]]+=a[i];

    }

    for(int i=;i<=n;i++)

    {

        LL op,l,r,w;

        scanf("%lld%lld%lld%lld",&op,&l,&r,&w);

        if(op==)

        add(l,r,w);

        else

        printf("%lld\n",get_sum(l,r)%(w+));

    }

    return ;

}