题目背景
无聊的 YYB 总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的 YYB 想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）
题目描述
维护一个数列 a i a_ia
i
，支持两种操作：
1 l r K D：给出一个长度等于 r − l + 1 r-l+1r−l+1 的 等差数列，首项为 K KK，公差为 D DD，并将它对应加到 [ l , r ] [l,r][l,r] 范围中的每一个数上。即：令 al=al+K,al+1=al+1+K+D…ar=ar+K+(r−l)×D
2 p：询问序列的第 p 个数的值 ap
输入格式
第一行两个整数数 n , m 表示数列长度和操作个数。
第二行 n 个整数，第 i 个数表示ai
接下来的 m mm 行，每行先输入一个整数 o p t optopt
若opt=1 则再输入四个整数 l r K D
若 opt=2 则再输入一个整数 p
输出格式
对于每个询问，一行一个整数表示答案。
输入输出样例
输入
5 2 1 2 3 4 5 1 2 4 1 2 2 3
输出
6
说明/提示
数据规模与约定
对于100% 数据，0 ≤ n , m ≤ 1 0 5 , − 200 ≤ a i , K , D ≤ 200 1≤l≤r≤n,1≤p≤n
根据差分很容易就可以想到：
在对区间[ l , r ] 加上一个首项为K ,公差为D 的等差数列之后，我们可以根据差分得到这样的式子：
a[l]=a[l]+K
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 其中，R + 1 ≤ n
对于要查询的答案，应该为a[p] + ∑ i = 1 p s u m [ i ] \sum_{i=1}^p sum[i]∑
i=1
p
sum[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\n", ans); } } return 0; } /** **/
