RE求助
查看原帖
RE求助
660776
ananran998楼主2023/5/19 23:38
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, m, a[100010], b[100010];
ll f[100010 * 4], v[100010 * 4];

inline void pushdown(int k, int l, int r) {
	v[k + k] += v[k];
	v[k + k + 1] += v[k];
	v[k] = 0;
}

inline void pushup(int k, int l, int r) {
	int m = (l + r) >> 1;
	f[k] = f[k + k] + v[k + k] * (m - l + 1) + f[k + k + 1] + v[k + k + 1] * (r - m);
}

inline void buildtree(int k, int l, int r) {
	v[k] = 0;
	if (l == r) {
		f[k] = b[l];
		return;
	}
	int m = (l + r) >> 1;
	buildtree(k + k, l, m);
	buildtree(k + k + 1, m + 1, r);
	pushup(k, l, r);
}

inline void add(int k, int l, int r, int x, int y, int d) {
	if (x > y)
		return;
	if (l == x && r == y) {
		v[k] += d;
		return;
	}
	pushdown(k, l, r);
	int m = (l + r) >> 1;
	if (y <= m)
		add(k + k, l, m, x, y, d);
	else if (x > m)
		add(k + k + 1, m + 1, r, x, y, d);
	else
		add(k + k, l, m, x, m, d), add(k + k + 1, m + 1, r, m + 1, y, d);
	pushup(k, l, r);
}

ll calc(int k, int l, int r, int x, int y) {
	if (l == x && r == y)
		return f[k] + v[k] * (r - l + 1);
	pushdown(k, l, r);
	int m = (l + r) >> 1;
	int res;
	if (y <= m)
		res = calc(k + k, l, m, x, y);
	else if (x > m)
		res = calc(k + k + 1, m + 1, r, x, y);
	else
		res = calc(k + k, l, m, x, m) + calc(k + k + 1, m + 1, r, m + 1, y);
	pushup(k, l, r);
	return res;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++)
		b[i] = a[i] - a[i - 1];
	buildtree(1, 1, n);
	while (m--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			int x, y, k, d;
			scanf("%d%d%d%d", &x, &y, &k, &d);
			add(1, 1, n, x, x, k);
			add(1, 1, n, y + 1, y + 1, -(k + (y - x) * d));
			add(1, 1, n, x + 1, y, d);
		} else {
			int x;
			scanf("%d", &x);
			printf("%lld\n", calc(1, 1, n, 1, x));
		}
	}
	return 0;
}
2023/5/19 23:38
加载中...