线段树73pts,求dalao帮调
查看原帖
线段树73pts,求dalao帮调
300098
cmaths楼主2022/7/31 21:57
#include <cstdio>
#define int long long

int n, m;
int ar[100005], sum[400005], lazy[400005];
void pushup(int x)
{
	sum[x] = sum[x * 2] + sum[x * 2 + 1];
}
void pushdown(int x, int l, int r)
{
	if(l == r)
	{
		return;
	}
	int lx = x * 2, rx = x * 2 + 1, mid = (l + r) / 2;
	if(lazy[x] != 0)
	{
		sum[lx] += (mid - l + 1) * lazy[x];
		sum[rx] += (r - mid) * lazy[x];
		lazy[lx] += lazy[x];
		lazy[rx] += lazy[x];
		lazy[x] = 0;
	}
}
void build(int x, int l, int r)
{
	if(l == r)
	{
		sum[x] = ar[l] - ar[l - 1];
		return;
	}
	int mid = (l + r) / 2;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	pushup(x);
}
void add(int x, int l, int r, int s, int t, int k)
{
	if(l >= s && r <= t)
	{
		sum[x] += (r - l + 1) * k;
		lazy[x] += k;
		return;
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	if(s <= mid)
	{
		add(x * 2, l, mid, s, t, k);
	}
	if(t > mid)
	{
		add(x * 2 + 1, mid + 1, r, s, t, k);
	}
	pushup(x);
}
int ask(int x, int l, int r, int s, int t)
{
	if(l >= s && r <= t)
	{
		return sum[x];
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2, ret = 0;
	if(s <= mid)
	{
		ret += ask(x * 2, l, mid, s, t);
	}
	if(t > mid)
	{
		ret += ask(x * 2 + 1, mid + 1, r, s, t);
	}
	return ret;
}
signed main()
{
	scanf("%lld %lld", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &ar[i]);
	}
	build(1, 1, n);
	for(int i = 1; i <= m; i++)
	{
		int op;
		scanf("%lld", &op);
		if(op == 1)
		{
			int l, r, K, D;
			scanf("%lld %lld %lld %lld", &l, &r, &K, &D);
			add(1, 1, n, l, l, K);
			add(1, 1, n, l + 1, r, D);
			add(1, 1, n, r + 1, r + 1, 0 - (K + (r - l) * D));
		}
		else
		{
			int p;
			scanf("%lld", &p);
			printf("%lld\n", ask(1, 1, n, 1, p));
		}
	}
	return 0;
}

马上要去睡觉了,可能明天才会看到qwq

感谢dalao! orz

2022/7/31 21:57
加载中...