题目背景
无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）
题目描述
维护一个数列 a i a_i ai ，支持两种操作：
1 l r K D：给出一个长度等于
r
−
l
+
1
r-l+1
r−l+1 的等差数列，首项为
K
K
K，公差为
D
D
D，并将它对应加到
[
l
,
r
]
[l,r]
[l,r] 范围中的每一个数上。即：令
a
l
=
a
l
+
K
,
a
l
+
1
=
a
l
+
1
+
K
+
D
…
a
r
=
a
r
+
K
+
(
r
−
l
)
×
D
a_l=a_l+K,a_{l+1}=a_{l+1}+K+Dldots a_r=a_r+K+(r-l) imes D
al=al+K,al+1=al+1+K+D…ar=ar+K+(r−l)×D
2 p：询问序列的第
p
p
p 个数的值
a
p
a_p
ap
输入格式
第一行两个整数数
n
,
m
n,m
n,m 表示数列长度和操作个数。
第二行
n
n
n 个整数，第
i
i
i 个数表示
a
i
a_i
ai
接下来的
m
m
m 行，每行先输入一个整数
o
p
t
opt
opt
若
o
p
t
=
1
opt=1
opt=1 则再输入四个整数
l
r
K
D
l r K D
l r K D
若
o
p
t
=
2
opt=2
opt=2 则再输入一个整数
p
p
p
输出格式
对于每个询问，一行一个整数表示答案。
输入输出样例
输入
5 2
1 2 3 4 5
1 2 4 1 2
2 3
输出
6
说明/提示
数据规模与约定
对于
100
%
100\%
100% 数据，
0
≤
n
,
m
≤
1
0
5
,
−
200
≤
a
i
,
K
,
D
≤
200
0le n,m le 10^5,-200le a_i,K,Dle 200
0≤n,m≤105,−200≤ai,K,D≤200,
1
≤
l
≤
r
≤
n
,
1
≤
p
≤
n
1 leq l leq r leq n, 1 leq p leq n
1≤l≤r≤n,1≤p≤n
根据差分很容易就可以想到：
在对区间
[
l
,
r
]
[l,r]
[l,r]加上一个首项为
K
K
K,公差为
D
D
D的等差数列之后，我们可以根据差分得到这样的式子：
a
[
l
]
=
a
[
l
]
+
K
a[l] = a[l] + K
a[l]=a[l]+K
a
[
i
]
=
a
[
i
]
+
D
a[i] = a[i] + D
a[i]=a[i]+D 其中
i
∈
[
l
+
1
,
r
]
i in [l+1,r]
i∈[l+1,r]
a
[
r
+
1
]
=
a
[
r
+
1
]
−
K
−
(
r
−
(
l
+
1
)
+
1
)
∗
D
a[r+1] = a[r+1] - K - (r - (l + 1) + 1) * D
a[r+1]=a[r+1]−K−(r−(l+1)+1)∗D 其中，
R
+
1
≤
n
R+1 leq n
R+1≤n
对于要查询的答案，应该为
a
[
p
]
a[p]
a[p] +
∑
i
=
1
p
s
u
m
[
i
]
sum_{i=1}^p sum[i]
∑i=1psum[i]
ac_code:
#define mid ((l + r) >> 1)
int n, m;
ll a[maxn << 2];
ll sum[maxn << 2];
ll lazy[maxn << 2];
void PushUp(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void PushDown(int rt, ll len) {
if (lazy[rt]) {
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1] += (len - (len >> 1)) * lazy[rt];
sum[rt << 1 | 1] += (len >> 1) * lazy[rt];
lazy[rt] = 0;
}
}
void Update(int rt, int l, int r, int L, int R, ll val) {
if (L <= l && r <= R) {
sum[rt] += (r - l + 1) * val;
lazy[rt] += val;
return;
}
PushDown(rt, r - l + 1);
int md = mid;
if (md >= L) Update(rt << 1, l, md, L, R, val);
if (md < R) Update(rt << 1 | 1, mid + 1, r, L, R, val);
PushUp(rt);
}
ll Query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) return sum[rt];
PushDown(rt, r - l + 1);
int md = mid;
ll ret = 0;
if (md >= L) ret += Query(rt << 1, l, md, L, R);
if (md < R) ret += Query(rt << 1 | 1, md + 1, r, L, R);
return ret;
}
int main() {
n = read, m = read;
for (int i = 1; i <= n; i++) a[i] = read;
ll L, R, K, D, op;
int p;
// puts("ok");
while (m--) {
op = read;
if (op == 1) {
L = read, R = read, K = read, D = read;
Update(1, 1, n, L, L, K);
if (L < R) Update(1, 1, n, L + 1, R, D);
ll tot = R - L;
if (R != n) Update(1, 1, n, R + 1, R + 1, -1 * (K + (tot * D)));
} else {
p = read;
ll ans = a[p] + Query(1, 1, n, 1, p);
printf("%lld
", ans);
}
}
return 0;
}
/**
**/