本蒟蒻连线段树都能写炸(悲)

0pts

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Tree
{
	ll left, right;
	ll sum, add;
}tree[400004];
ll a[100001];
void Build(ll l, ll r, ll k)
{
	tree[k].left = l;
	tree[k].right = r;
	if(l == r)
	{
		tree[k].sum = a[l];
		return ;
	}
	ll mid = l + r >> 1;
	Build(l, mid, 2 * k);
	Build(mid + 1, r, 2 * k + 1);
	tree[k].sum = tree[k * 2].sum + tree[k * 2 + 1].sum;
	return ; 
}
void Change(ll k, ll v)
{
	tree[k].sum = (tree[k].right - tree[k].left + 1) * v;
	tree[k].add += v;
	return ;
}
void Pushdown(ll k)
{
	Change(2 * k, tree[k].add);
	Change(2 * k + 1, tree[k].add);
	tree[k].add = 0;
	return ;
}
ll Query(ll l, ll r, ll k)
{
	if(tree[k].left >= l && tree[k].right <= r)
	{
		return tree[k].sum;
	}
	Pushdown(k);
	ll mid = tree[k].left + tree[k].right >> 1;
	ll res = 0;
	if(l <= mid)
		res += Query(l, r, 2 * k);
	if(r > mid)
		res += Query(l, r, 2 * k + 1);
	return res;
}
void Update(ll l, ll r, ll v, ll k)
{
	if(tree[k].left >= l && tree[k].right <= r)
	{
		Change(k, v);
		return ;
	}
	Pushdown(k);
	ll mid = tree[k].left + tree[k].right >> 1;
	if(l <= mid)
		Update(l, r, v, 2 * k);
	if(r > mid)
		Update(l, r, v, k * 2 + 1);
	tree[k].sum = tree[k * 2].sum + tree[k * 2 + 1].sum;
	return ;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);     cout.tie(0);
	ll n, m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	Build(1, n, 1);
	while(m--)
	{
		ll op, x, y, k;
		cin >> op >> x >> y;
		if(op == 1)
		{
			cin >> k;
			Update(x, y, k, 1);
		}
		else
		{
			cout << Query(x, y, 1) << "\n";
		}
	}
	return 0;
}