LibreOJ 6277. 数列分块入门 1

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

参考博客：https://www.cnblogs.com/stxy-ferryman/p/8547731.html

两个操作，区间增加和单点查询。

思路：将整个数组按照block（block=sqrt(n)）分成许多小块，lump[i]表示点i所在的块，tag[i]表示编号为i的块的增加值，如果是进行区间增加操作，我们一般可以把区间[l,r]分成三个部分，左边不完整的区间（只含有某块中的部分点），中间完整的区间（含有一些块的所有点），右边不完整的区间。这样对于左右的不完整区间，他们的点的数量是比较少的，我们可以进行暴力更新，对于中间的完整区间，一般来说他们的点比较多，我们就用标记数组tag[i]来记录第i块里增加的数，从而避免对太多的点进行单点更新。在单点查询时，某个点的值就是本身数组的值加上这个点所在的块的标记数组值（a[r]+tag[lump[r]）。

点i所在的块是lump[i]=(i-1)/block+1，表示lump[i]=i/block+1。

假设现在n=9，那么block=sqrt(9)=3。

对1到9之间的点分块，在i=3时，错误：3/3+1=2，3就在第二组  ，但是这是不对的，按理说3应该在第一组，怎么办，把3减1....

代码：

#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 50005

/*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;

}*/

int tag[maxn],a[maxn],lump[maxn];

int n,m,k,t,block;

void add(int l,int r,int c)//这里注意要把各个块的边界写正确

{

    for(int i=l;i<=min(lump[l]*block,r);i++)//左边的不完整的块  暴力更新每个点

    a[i]+=c;

    if(lump[l]!=lump[r])//左边界和右边界不在一个块里面

    {

        for(int i=(lump[r]-)*block+;i<=r;i++)//右边的不完整的块  暴力更新

        a[i]+=c;

    }

    for(int i=lump[l]+;i<=lump[r]-;i++)//中间的完整的块的标记数组  增加值

    tag[i]+=c;

}

int main()

{

    scanf("%d",&n);

    block=sqrt(n);

    fill(tag,tag+maxn-,);

    for(int i=;i<=n;i++)//给每个点分块

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

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

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

    int op,l,r,c;

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

    {

        scanf("%d%d%d%d",&op,&l,&r,&c);

        if(op==)

        add(l,r,c);

        else

        printf("%d\n",a[r]+tag[lump[r]]);

    }

    return ;

}