原题链接
- 题意和思路：挺有意思的一道题，就是两个操作，第一个操作是在 (l) 到 (r) 的区间上加上首项为 (k)，公比为 (d) 的等差序列。第二个操作是询问第 (x) 个数是多少。其实就是区间修改 (+) 区间查询，操作一就是在 (l) 上加上 (k)，然后在 (l + 1) 到 (r) 上加上 (d)，然后在 (r + 1) 上减去 ((r-(l + 1)-1) imes d + k)。需要注意的是，小心要是 (r + 1 > n) 会出现奇怪的错误，所以要细心边界。
- 代码：
#include <cstdio>
#include <iostream>
using namespace std;
const ll inf = 0x3f3f3f3f;
const ll N = 1e5 + 9;
int a[N];
int sum[N];
struct segment_tree {
struct node {
int l, r, L, R, data, lazy;
} tr[N << 2];
inline void pushup(int p) {tr[p].data = tr[tr[p].l].data + tr[tr[p].r].data;}
inline void pushdown(int p) {
if (tr[p].lazy == 0) return;
tr[tr[p].l].data += (tr[tr[p].l].R - tr[tr[p].l].L + 1) * tr[p].lazy;
tr[tr[p].r].data += (tr[tr[p].r].R - tr[tr[p].r].L + 1) * tr[p].lazy;
tr[tr[p].l].lazy += tr[p].lazy;
tr[tr[p].r].lazy += tr[p].lazy;
tr[p].lazy = 0;
return;
}
inline void build(int l, int r, int p) {
tr[p].L = l, tr[p].R = r;
tr[p].l = p << 1;
tr[p].r = p << 1 | 1;
if (l == r) {
tr[p].data = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, tr[p].l);
build(mid + 1, r, tr[p].r);
pushup(p);
}
inline void add(int l, int r, int num, int p) {
if (tr[p].L >= l && tr[p].R <= r) {
tr[p].data += num * (tr[p].R - tr[p].L + 1);
tr[p].lazy += num;
return;
}
pushdown(p);
int mid = l + r >> 1;
if (tr[tr[p].l].R >= l) add(l, r, num, tr[p].l);
if (tr[tr[p].r].L <= r) add(l, r, num, tr[p].r);
pushup(p);
}
inline int ask(int l, int r, int p) {
if (tr[p].L >= l && tr[p].R <= r) {
return tr[p].data;
}
pushdown(p);
int ret = 0;
if (tr[tr[p].l].R >= l) ret += ask(l, r, tr[p].l);
if (tr[tr[p].r].L <= r) ret += ask(l, r, tr[p].r);
return ret;
}
} T;
signed main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
T.build(1, n, 1);
while (m--) {
int op;
scanf("%d", &op);
if (op == 1) {
int l, r, k, d;
scanf("%d%d%d%d", &l, &r, &k, &d);
T.add(l, l, k, 1);
if (r != l) T.add(l + 1, r, d, 1);
int sub = (r - (l + 1) + 1) * d + k;
if (r + 1 <= n)
T.add(r + 1, r + 1, -sub, 1);
} else {
int x;
scanf("%d", &x);
printf("%d
", T.ask(1, x, 1) - sum[x - 1]);
}
}
}