求助模板
查看原帖
求助模板
758985
kunkun127楼主2025/1/24 16:25

全RE,找不出哪里有错qaq

#include <bits/stdc++.h>
#define hyh using
#define love namespace
#define lsq std
hyh love lsq;
hyh LL = long long;
const int hyh_lover = 647, MAXN = 100005;
int a[MAXN], sum[MAXN << 2], tag[MAXN << 2];

int ls(int p) { return p << 1; }//左儿子 
int rs(int p) { return p << 1 | 1; };//右儿子

void add(int k, int l, int r, LL v)
{
	sum[k] += (r - l + 1) * v;
	tag[k] += v;
}

void push_up(int p) { sum[p] = sum[ls(p)] + sum[rs(p)]; }

void push_down(int k, int l, int r)
{
	int mid = (l + r) >> 1;
	add(ls(k), l, mid, tag[k]);
	add(rs(k), mid + 1, r, tag[k]);
	tag[k] = 0;
}

void update(int k, int l, int r, int ql, int qr, int v)
{
	if (ql <= l && r <= qr) return add(k, l, r, v);
	push_down(k, l, r);
	int mid = (l + r) >> 1;
	if (ql <= mid) update(ls(k), l, mid, ql, qr, v);
	if (ql <= mid) update(rs(k), mid + 1, r, ql, qr, v);
	push_up(k);
}

void build(LL l, LL r, LL p)//递归建树 
{
	if (l == r) return add(p, l, r, a[l]);
	int mid = (l + r) >> 1;
	build(ls(p), l, mid); build(rs(p), mid + 1, r);
	push_up(p);//由于我们是要通过子节点来维护父亲节点,所以pushup的位置应当是在回溯时 
}

LL query(int k, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr) return sum[k];
	push_down(k, l, r);
	int mid = (l + r) >> 1;
	LL ans = 0;
	if (ql <= mid) ans += query(ls(k), l, mid, ql, qr);
	if(mid < qr) ans += query(rs(k), mid + 1, r, ql, qr);
	return ans;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	build(1, 1, n);
	while (m--)
	{
		LL q;
		cin >> q;
		if (q == 1)
		{
			LL b, c, d;
			cin >> b >> c >> d;
			update(1, 1, n, b, c, d); 
		}
		else
		{
			LL b, c;
			cin >> b >> c;
			cout << query(1, 1, n, b, c) << endl; 
		}
	}
	return !(hyh_lover == 647);
}

2025/1/24 16:25
加载中...