社区讨论

全部RE,佬们可以帮我看看吗

P2357守墓人参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2v6o2j
此快照首次捕获于
2023/10/23 20:18
2 年前
此快照最后确认于
2023/10/23 20:18
2 年前
查看原帖
CPP
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10;
typedef long long ll;
ll n , m , a[N];

struct tree{
	ll l , r , sum , lazy;
}tr[4 * N];

void pushup(ll u){
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(ll u){
	if(tr[u].lazy){
		tr[u << 1].lazy += tr[u].lazy , tr[u << 1 | 1].lazy += tr[u].lazy;
		tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy , tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
		tr[u].lazy = 0;
	}
}

void build(ll u,ll l,ll r){
	tr[u].lazy = 0;
	if(l == r) tr[u] = { l , r , a[r] , 0};
	else{
		tr[u] = {l , r};
		ll mid = l + r >> 1;
		build(u << 1 , 1 , mid) , build(u << 1 | 1 , mid + 1 , r);
		pushup(u);
	}
}

void modify(ll u , ll l , ll r , ll v){
	if(l <= tr[u].l && tr[u].r <= r){
		tr[u].sum += (tr[u].r - tr[u].l + 1) * v;		
		tr[u].lazy += v;		
	}
	else{
		pushdown(u);
		ll mid = tr[u].l + tr[u].r >> 1;
		if(l <= mid) modify(u << 1 , l , r , v);
		if(r > mid) modify(u << 1 | 1 , l , r , v);
		pushup(u);
	}
}

ll query(ll u,ll l,ll r){
	if(l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
	else{
		ll mid = tr[u].l + tr[u].r >> 1;
		ll tot = 0;
		if(l <= mid) tot = query(u << 1 , l , r);
		if(r > mid) tot += query(u << 1 | 1 , l , r);
		return tot;
	}
}

int main()
{
	cin >> n >> m;
	for (int i = 1 ; i <= n ; ++i) cin >> a[i];
	
	build(1 , 1 , n);
	
	while(m--)
	{
		int op , l , r , c , k;
		cin >> op;
		if(op == 1){
			cin >> l >> r >> c;
			modify(1 , l , r , c);
		}else if(op == 2){
			cin >> k;
			modify(1 , 1 , 1 , k);
		}else if(op == 3){
			cin >> k;
			modify(1 , 1 , 1 , -k);
		}else if(op == 4){
			cin >> l >> r;
			cout << query(1 , l , r) << endl;
		}else {
			cout << query(1 , 1 , 1) << endl;
		}
	}
	
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...