数列分块入门 1 LibreOJ - 6277
给出一个长为 nn 的数列，以及 nn 个操作，操作涉及区间加法，单点查值。
Input
第一行输入一个数字 nn。
第二行输入 nn 个数字，第 ii 个数字为 aiai，以空格隔开。
接下来输入 nn 行询问，每行输入四个数字 optopt、ll、rr、cc，以空格隔开。
若 opt=0opt=0，表示将位于 [l,r][l,r] 的之间的数字都加 cc。
若 opt=1opt=1，表示询问 arar 的值（ll 和 cc 忽略）。
Output
对于每次询问，输出一行一个数字表示答案。
Example
样例输入
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
样例输出
2
5
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <string>
5 #include <vector>
6 #include <map>
7 #include <set>
8 #include <list>
9 #include <deque>
10 #include <queue>
11 #include <stack>
12 #include <cstdlib>
13 #include <cstdio>
14 #include <cmath>
15 #include <iomanip>
16 #define ull unsigned long long
17 #define ll long long
18 #define pb push_back
19 #define rep(i,start,end) for(int i=start;i<=end;i++)
20 #define per(i,end,start) for(int i=end;i>=start;i--)
21 #define tle ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
22 #define lc now<<1
23 #define rc now<<1|1
24 ll read()
25 {
26 ll x=0,f=1;char ch=getchar();
27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
28 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
29 return x*f;
30 }
31 using namespace std;
32 const int mod = 1000000007 ; ///998244353;
33 const int mxn = 2e5 +7;
34 ll _,n,m,t,k,u,v,ans,cnt,ok,lim,len;
35 int a[mxn] ,inv[mxn],lazy[mxn],id[mxn];
36 void up(int l,int r,int c)
37 {
38 for(int i=l;i<=min(id[l]*len,1ll*r);i++) a[i]+=c;
39 if(id[l]!=id[r])
40 for(int i=(id[r]-1)*len+1;i<=r;i++)
41 a[i]+=c;
42 for(int i=id[l]+1;i<=id[r]-1;i++) lazy[i]+=c;
43 }
44 int main()
45 {
46 n = read() ;
47 len = sqrt(n);
48 for(int i=1;i<=n;i++) a[i] = read();
49 for(int i=1;i<=n;i++) id[i] = (i-1)/len + 1 ;
50 int l,r,c,op;
51 for(int i=1;i<=n;i++)
52 {
53 op = read() ; l = read() ; r=read();c=read();
54 if(!op) up(l,r,c);
55 else cout<<a[r] + lazy[ id[r] ]<<endl;
56 }
57 }