动态开点求调,悬 1 关
查看原帖
动态开点求调,悬 1 关
693428
unDefined_Future楼主2023/11/22 22:20

0 分,样例过了,但是自己手造的数据都过不了 qwq。

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

ll n, m;
const int N = 100010, N2 = N * 2;
ll a[N];
ll ls[N2], rs[N2], root, idx;
ll sum[N2], lzy[N2];

void makeNode(int l, int r, ll &k) {
	if(k == 0) {
		k = ++idx;
		if(l == r) sum[k] = a[l];
	}
}

void pushUp(ll k) {
	sum[k] = sum[ls[k]] + sum[rs[k]];
}

void pushDown(int l, int r, ll k) {
	int mid = (l + r) >> 1;
	if(lzy[k]) {
		ll c = lzy[k]; lzy[k] = 0;
		makeNode(l, mid, ls[k]), makeNode(mid + 1, r, rs[k]);
		sum[ls[k]] += c * (mid - l + 1); sum[rs[k]] += c * (r - mid);
		lzy[ls[k]] += c, lzy[rs[k]] += c;
	}
}

void upd(int l, int r, ll &k, int L, int R, int c) {
	makeNode(l, r, k);
	if(L <= l && r <= R) {
		sum[k] += (r - l + 1) * c;
		lzy[k] += c;
		return;
	}
	pushDown(l, r, k);
	int mid = (l + r) >> 1;
	if(L <= mid) upd(l, mid, ls[k], L, R, c);
	if(mid < R) upd(mid + 1, r, rs[k], L, R, c);
	pushUp(k);
}

ll query(int l, int r, ll &k, int L, int R) {
	makeNode(l, r, k);
	if(L <= l && r <= R) return sum[k];
	pushDown(l, r, k);
	int mid = (l + r) >> 1; ll res = 0;
	if(L <= mid) res += query(l, mid, ls[k], L, R);
	if(mid < R) res += query(mid + 1, r, rs[k], L, R);
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while(m--) {
		int opt; cin >> opt;
		if(opt == 1) {
			int l, r; ll c; cin >> l >> r >> c;
			upd(1, n, root, l, r, c);
		} else {
			int l, r; cin >> l >> r;
			cout << query(1, n, root, l, r) << endl;
		}
//		for (int i = 1; i <= n; i++) cout << query(1, n, root, i, i) << ' ';
//		cout << endl;
	}
	return 0;
}

要离开机房了,消息可能会明天才能回,见谅。

2023/11/22 22:20
加载中...