RE求调
查看原帖
RE求调
589190
YLgiegie楼主2024/5/5 17:05

目测是build有问题,麻烦大佬看一下(如果能看出来其他错误更好)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 +10;
ll n , m , q;

ll a[N];
struct node{
	ll num;
	ll ls , rs;
	ll lazy;
}tr[N];
#define lson tr[rt].ls
#define rson tr[rt].rs
#define mid (lson + rson) >> 1
void build(ll rt , ll l , ll r) {
	lson = l;
	rson = r;
	if(l == r) {
		tr[rt].num = a[l];
		return;
	}
	build(rt << 1 , l , mid);
	build(rt << 1 | 1, mid + 1 , r);
	tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
void push(ll rt) {
	ll lazy = tr[rt].lazy;
	if(lazy) {
		tr[rt << 1].num += lazy * (tr[rt << 1].rs + tr[rt << 1].ls + 1);
		tr[rt << 1].lazy += lazy;
		tr[rt << 1 | 1].num += lazy * (tr[rt << 1 | 1].rs + tr[rt << 1 | 1].ls + 1);
		tr[rt << 1 | 1].lazy += lazy;
		tr[rt].lazy = 0;
	}
}

void update(ll rt , ll l , ll r , ll v) {
	if(l <= lson && r >= rson) {
		tr[rt].num += v * (lson + rson + 1);
		tr[rt].lazy += v;
		return;
	}
	push(rt);
	if(l <= mid) update(rt << 1 , l , r , v);
	if(r > mid) update(rt << 1 | 1 , l , r , v);
	tr[rt].num = tr[rt << 1].num + tr[rt << 1 | 1].num;
}
ll query(ll rt , ll l , ll r) {
	if(l <= lson && r >= rson) return tr[rt].num;
	push(rt);
	ll ans = 0;
	if(l <= mid) ans += query(rt << 1 , l , r);
	if(r > mid) ans += query(rt << 1 | 1 , l , r);
	return ans;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n ; i++) {
		cin >> a[i];
	}
	build(1 , 1 , n);
	while(m--) {
		ll op , x , y , h;
		cin >> op;
		if(op == 1) {
			cin >> x >> y >> h;
			update(1 , x , y , h);
		}
		else {
			cin >> x >> y;
			query(1 , x , y);
		}
	}
}
2024/5/5 17:05
加载中...