LOJ#6277. 数列分块入门 1

分块思想，先把原来的序列分成根号n快，然后对于更新的部分，先操作这个序列边上的部分，然后再中间部分整块操作，这样复杂度就是O(根号N)

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define first fi

#define second se

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = ;

using namespace std;

int n, m, tol, T;

int block;

int bel[maxn];

int a[maxn];

int add[maxn];

void init() {

    memset(a, , sizeof a);

    memset(add, , sizeof add);

    memset(bel, , sizeof bel);

}

void update(int l, int r, int c) {

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

        a[i] += c;

    if(bel[l] != bel[r]) {

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

            a[i] += c;

    }

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

        add[i] += c;

}

int main() {

    while(~scanf("%d", &n)) {

        init();

        block = sqrt(n);

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

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

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

        }

        m = n;

        while(m--) {

            int op, l, r, c;

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

            if(op == ) {

                update(l, r, c);

            } else {

                printf("%d\n", a[r] + add[bel[r]]);

            }

        }

    }

    return ;

}