非差分普通线段树WA9pts求条
查看原帖
非差分普通线段树WA9pts求条
682196
2022dyxwitHLove楼主2024/8/8 11:53
#include <bits/stdc++.h>
#define int long long
#define mid ((l + r) >> 1)
#define ls (x << 1)
#define rs ((x << 1) + 1)
using namespace std;
const int N = 4e5 + 5;
int n, m, a[N];
struct Node{
	int val;
	int lazk;
	int lazd;
}tree[N];
void pushup(int x) {
	tree[x].val = tree[ls].val + tree[rs].val;
}
void pushdown(int l, int r, int x) {
	tree[ls].val += (mid - l + 1) * tree[x].lazk + (mid - l) * (mid - l + 1) * tree[x].lazd / 2;
	tree[ls].lazk += tree[x].lazk;
	tree[ls].lazd += tree[x].lazd;
	tree[rs].val += (r - mid) * (tree[x].lazk + (mid - l + 1) * tree[x].lazd) + (r - mid - 1) * (r - mid) * tree[x].lazd / 2;
	tree[rs].lazk += tree[x].lazk + (mid - l + 1) * tree[x].lazd;
	tree[rs].lazd += tree[x].lazd;
	tree[x].lazk = tree[x].lazd = 0;
}
void build(int l, int r, int x) {
	if (l == r) {
		tree[x].val = a[l];
		return;
	}
	build(l, mid, ls);
	build(mid + 1, r, rs);
	pushup(x);
}
void modify(int l, int r, int x, int y, int z, int k, int d) {
	if (y <= l && r <= z) {
		tree[x].val += (r - l + 1) * k + (r - l) * (r - l + 1) * d / 2;
		tree[x].lazk += k;
		tree[x].lazd += d;
		return;
	}
	pushdown(l, r, x);
	if (y <= mid) modify(l, mid, ls, y, z, k, d);
	if (z > mid) modify(mid + 1, r, rs, y, z, k + (mid - max(l, y) + 1) * d, d);
	pushup(x);
}
int query(int l, int r, int x, int y) {
	if (l == r) return tree[x].val;
	pushdown(l, r, x);
	if (y <= mid) return query(l, mid, ls, y);
	return query(mid + 1, r, rs, y);
}
signed main() {
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build(1, n, 1);
	for (int i = 1, op, l, r, x, y; i <= m; ++i) {
		cin >> op;
		if (op == 1) {
			cin >> l >> r >> x >> y;
			modify(1, n, 1, l, r, x, y);
		}
		if (op == 2) {
			cin >> x;
			cout << query(1, n, 1, x) << '\n';
		}
	}
}
2024/8/8 11:53
加载中...