数列分块入门 1 LOJ6277

题目描述

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 iii 个数字为 ai，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。

若 opt=1，表示询问 ar 的值（ll和 c忽略）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

样例输入

样例输出

2

5

题解：

分块写法

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int MAXN=50000+10;

ll a[MAXN];

int block,num;  //块大小 块数量

int belong[MAXN],l[MAXN],r[MAXN];//归属那一块，块左右端点

ll sum[MAXN]; // 块的信息修改

int n;

void build()

{

    block=sqrt(n);

    num=n/block;

    if(n%block!=0) 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 updata(int x,int y,int c)

{

    for (int i = x; i <=min(r[belong[x]],y) ; ++i) {// 注意此处取两者最小值

        a[i]+=c;

    }

    if(belong[x]!=belong[y])

        for (int i = l[belong[y]]; i <=y ; ++i) {

            a[i]+=c;

        }

    for (int i = belong[x]+1; i <=belong[y]-1 ; ++i) {

        sum[i]+=c;

    }

}

ll ask(int x)

{

    return a[x]+sum[belong[x]];

}

int main()

{

    scanf("%d",&n);

    memset(sum,0, sizeof(sum));

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

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

    }

    int op,x,y,c;

    build();

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

        scanf("%d%d%d%d",&op,&x,&y,&c);

        if(op==0)

        {

            updata(x,y,c);

        } else

        {

            printf("%lld\n",ask(y));

        }

    }

    return 0;

}

巴特西