LOJ-6277 数列分块入门1

Description

给定一个长为$n$的数列，以及$n$个操作，操作涉及区间加法、单点查询。

Input

第一行输入一个数字$n$。 第二行输入$n$个数字，第$i$个数字为$a_i$，以空格隔开。 接下来输入$n$行询问，每行输入四个数字$opt$、$l$、$r$、$c$，以空格隔开。 若$opt=0$，表示将位于$[l，r]$的之间的数字都加$c$。 若$opt=1$，表示询问$a_r$的值（$l$和$c$忽略）。

对于$100\% <span><span class="MathJax_Preview">的数据，</span><script type="math/tex">的数据，$1 \leq n \leq 50000,-2^{31} \leq \text { others, ans } \leq 2^{31}-11 \leq n \leq 50000,-2^{31} \leq \text { others, ans } \leq 2^{31}-1

Output

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

Sample Input

4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

Sample Output

2
5

---

#include <bits/stdc++.h>

using namespace std;

int n, len; //数列长度，块的长度
vector<int> seq(50005); //存储数列元素
vector<int> belong(50005); //记录每个元素属于哪一个块
vector<int> addSign(50005); //加法标记

//区间加法
inline void add(int l, int r, int c)
{
    //左边不完整的块元素值直接改变
    for (int i = l; i <= min(belong[l] * len, r); ++i) seq[i] += c;
    //右边不完整的块元素值直接改变    
    if (belong[l] != belong[r]) { //确保l和r不在同一个块内
        for (int i = (belong[r] - 1) * len + 1; i <= r; ++i) seq[i] += c;
    }
    //改变中间整块的加法标记
    for (int i = belong[l] + 1; i <= belong[r] - 1; ++i) addSign[i] += c;
}

//单点查询
inline int query(int pos)
{
    return seq[pos] + addSign[belong[pos]];
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    len = sqrt(n); //计算每个块的长度
    for (int i = 1; i <= n; ++i) {
        cin >> seq[i];
        belong[i] = (i - 1) / len + 1; //确定每个元素属于哪个块
    }

    int opt, l, r, c;
    for (int i = 0; i < n; ++i) {
        cin >> opt >> l >> r >> c;
        if (opt & 1) cout << query(r) << endl;
        else add(l, r, c);
    }

    return 0;
}