拿动态开点做的,10分,求调
查看原帖
拿动态开点做的,10分,求调
843875
Aewrxuk楼主2023/6/8 14:22
#include <bits/stdc++.h>
#define int long long
#define M 2001000
using namespace std;
struct node {
	int l, r, lc, rc, lazy, sum;
} tree[M<<1];
string op;
int num, n, m, a, x, y, z, root; 
void build(int &id, int l, int r, int x, int k) {
	if (!id) id = ++num;
	tree[id].l = l, tree[id].r = r;
	if (l == r) {
		tree[id].sum = k;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) build(tree[id].lc, l, mid, x, k);
	else build(tree[id].rc, mid+1, r, x, k);
	tree[id].sum = tree[tree[id].lc].sum + tree[tree[id].rc].sum;
}
void pushdown(int id) {
	if (tree[id].lazy) {
//		if (!tree[id].lc) tree[id].lc = ++num;
//		if (!tree[id].rc) tree[id].rc = ++num;
		int mid = (tree[id].l + tree[id].r) >> 1;
		tree[tree[id].lc].lazy += tree[id].lazy;
		tree[tree[id].rc].lazy += tree[id].lazy;
		tree[tree[id].lc].sum += (mid - tree[id].l + 1) * tree[tree[id].lc].lazy;
		tree[tree[id].rc].sum += (tree[id].r - mid) * tree[tree[id].rc].lazy;
		tree[id].lazy = 0;
	}
}
void change(int id, int l, int r, int k) {
	if (tree[id].r < l || tree[id].l > r) return;
	//if (!id) id = ++num;
	if (l <= tree[id].l && tree[id].r <= r) {
		tree[id].sum += (tree[id].r - tree[id].l + 1) * k;
		tree[id].lazy += k;
		return;
	}
	pushdown(id);
	int mid = (tree[id].l + tree[id].r) >> 1;
	change(tree[id].lc, l, r, k);
	change(tree[id].rc, l, r, k);
	tree[id].sum = tree[tree[id].lc].sum + tree[tree[id].rc].sum;
}
int query(int id, int l, int r) {
	if (tree[id].l == l && tree[id].r == r) return tree[id].sum;
	pushdown(id);
	int mid = (tree[id].l + tree[id].r) >> 1;
	if (r <= mid) return query(tree[id].lc, l, r);
	else if (l > mid) return query(tree[id].rc, l, r);
	else return query(tree[id].lc, l, mid) + query(tree[id].rc, mid+1, r);
}
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		build(root, 1, n, i, a);
	}
	cin >> m;
	while (m--) {
		cin >> op;
		if (op == "ADD") {
			cin >> x >> y >> z;
			change(root, x, y, z);
		} else {
			cin >> x >> y;
			cout << query(root, x, y) << endl;
		}
	}
	return 0;
}
2023/6/8 14:22
加载中...