社区讨论
维护首项及公差做法,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;
}
在和的时候主要思路为:
对于左子段,相当于加上了从首项为, 公差为的等差数列;但对于右子段,其实也就是把首项改为了左子段的末项加,其余不变
回复
共 2 条回复,欢迎继续交流。
正在加载回复...