社区讨论

维护首项及公差做法,0pts,求助

P1438无聊的数列参与者 1已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lob6mwbi
此快照首次捕获于
2023/10/29 16:01
2 年前
此快照最后确认于
2023/11/02 10:52
2 年前
查看原帖
代码:
CPP
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5+10;
struct Node
{
	int l, r;
	int sum, k, d;
} tr[N << 2];
int n, m, a[N];
int get(int k, int d, int len)
{
	if(len % 2 == 0) return len / 2 * (k + k + d * (len - 1));
	else return len / 2 * (k + k + d * (len - 1)) + k + (len / 2) * d;
}
void push_up(Node &u, Node &l, Node &r)
{
	u.sum = l.sum + r.sum;
}
void push_down(Node &u, Node &l, Node &r)
{
	if(u.k == 0 && u.d == 0) return;
	l.sum += get(u.k, u.d, l.r - l.l + 1);
	r.sum += get(u.k + u.d * (l.r - l.l + 1), u.d, r.r - r.l + 1);
	l.k += u.k, r.k += u.k;
	u.k = u.d = 0;
}
void build(int p, int l, int r)
{
	tr[p] = {l, r};
	if(l == r)
	{
		tr[p].sum = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(2 * p, l, mid);
	build(2 * p + 1, mid + 1, r);
	push_up(tr[p], tr[2 * p], tr[2 * p + 1]);
}
int query(int p, int k)
{
	if(tr[p].l == tr[p].r)
		return tr[p].sum;
	push_down(tr[p], tr[2 * p], tr[2 * p + 1]);
	int mid = tr[p].l + tr[p].r >> 1;
	if(k <= mid) return query(2 * p, k);
	else return query(2 * p + 1, k);
}
void modify(int p, int l, int r, int k, int d)
{
	if(l <= tr[p].l && tr[p].r <= r)
	{
		tr[p].sum += get(k, d, tr[p].r - tr[p].l + 1);
		tr[p].k += k, tr[p].d += d;
		return;
	}
	push_down(tr[p], tr[2 * p], tr[2 * p + 1]);
	int mid = tr[p].l + tr[p].r >> 1;
	if(l <= mid) modify(2 * p, l, r, k, d);
	if(r > mid && l <= mid) modify(2 * p + 1, l, r, k + d * (mid - l + 1), d);
	if(l > mid && r > mid) modify(2 * p + 1, l, r, k, d);
	push_up(tr[p], tr[2 * p], tr[2 * p + 1]);
}
int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++)
			scanf("%d", &a[i]);
	build(1, 1, n);
	while(m --)
	{
		int op, l, r, k, d;
		scanf("%d%d", &op, &l);
		if(op == 1) 
		{
			scanf("%d%d%d", &r, &k, &d);
			modify(1, l, r, k, d);
		} else printf("%d\n", query(1, l));
	}
	return 0;
}
pushdownpushdownmodifymodify的时候主要思路为: 对于左子段,相当于加上了从首项为kk, 公差为dd的等差数列;但对于右子段,其实也就是把首项kk改为了左子段的末项加dd,其余不变

回复

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

正在加载回复...