样例输出0,不知道哪里错
查看原帖
样例输出0,不知道哪里错
550570
JanF楼主2023/8/30 17:30
//真·加等差数列
#include <bits/stdc++.h>
#define ls p << 1
#define rs p << 1 | 1
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
ll a[N], n, q, b[N];
struct node
{
    int l, r;
    ll sum, add;
} tr[4 * N];

void pushup(int p)
{
    tr[p].sum = tr[ls].sum + tr[rs].sum;
}

void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r, tr[p].add = 0;
    if (l == r)
    {
        tr[p].sum = b[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}

void pushdown(int p, int a)
{
    int l = tr[p].l, r = tr[p].r;
    int mid = (l + r) >> 1;
    tr[ls].sum += (mid - l + 1) * a;
    tr[rs].sum += (r - mid) * a;
    tr[ls].add += a;
    tr[rs].add += a;
    tr[p].add = 0;
}

void update(int p, int ql, int qr, int c) //区间加
{
    if (ql <= tr[p].l && tr[p].r <= qr)
    {
        tr[p].sum += (tr[p].r - tr[p].l + 1) * c;
        tr[p].add += c;
        return;
    }
    pushdown(p, c);
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (ql <= mid)
        update(ls, ql, qr, c);
    if (qr > mid)
        update(rs, ql, qr, c);
    pushup(p);
}

ll query(int p, int ql, int qr) //区间和
{
    if (ql <= tr[p].l && tr[p].r <= qr)
        return tr[p].sum;
    int mid = (tr[p].l + tr[p].r) >> 1;
    ll ans = 0;
    if (ql <= mid)
        ans += query(ls, ql, qr);
    if (qr > mid)
        ans += query(rs, ql, qr);
    return ans;
}

int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i] - a[i - 1];
    build(1, 1, n);
    while (q--)
    {
        int l, r, k, d;
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            cin >> l >> r >> k >> d;
            update(1, l, l, k);
            if (l + 1 <= r)
                update(1, l + 1, r, d);
            if (r < n)
                update(1, r + 1, r + 1, -(k + (r - l) * d));
        }
        else
        {
            int p;
            cin >> p;
            cout << query(1, 1, p) << endl;
        }
    }
    return 0;
}
2023/8/30 17:30
加载中...