线段树二次差分,只过了第一个点,遇到负数不行
  • 板块P1438 无聊的数列
  • 楼主BIOS
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/12/21 23:30
  • 上次更新2023/12/21 23:34:00
查看原帖
线段树二次差分,只过了第一个点,遇到负数不行
833124
BIOS楼主2023/12/21 23:30

RT,求助,感觉没啥问题貌似

#include <iostream>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, m, op, l, r, k, d, x, w[N], num[N];
struct node
{
    int l, r, sum, add;
} tr[N << 2];
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, right.add += root.add;
        left.sum += root.add * (left.r - left.l + 1);
        right.sum += root.add * (right.r - right.l + 1);
        root.add = 0;
    }
}
void build(int u, int l, int r)
{
    if (l == r)
        return tr[u] = {l, l, w[l], 0}, void();
    int mid = l + r >> 1;
    tr[u].l = l, tr[u].r = r;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify_seg(int u, int v, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].add += v, tr[u].sum += v * (tr[u].r - tr[u].l + 1), void();
    int mid = tr[u].l + tr[u].r >> 1;
    pushdown(u);
    if (l <= mid)
        modify_seg(u << 1, v, l, r);
    if (r > mid)
        modify_seg(u << 1 | 1, v, l, r);
    pushup(u);
}
int query(int u, int l, int r)
{
    if (l <= tr[u].l && tr[u].r <= r)
        return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    pushdown(u);
    if (l <= mid)
        res += query(u << 1, l, r);
    if (r > mid)
        res += query(u << 1 | 1, l, r);
    return res;
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> num[i], w[i] = num[i] - num[i - 1];
    build(1, 1, n);
    while (m--)
    {
        cin >> op;
        if (op == 2)
            cin >> x, cout << query(1, 1, x) << "\n";
        else
        {
            cin >> l >> r >> k >> d;
            modify_seg(1, k, l, l);
            if (l + 1 <= r)
                modify_seg(1, d, l + 1, r);
        }
    }
}
2023/12/21 23:30
加载中...