社区讨论

蒟蒻0分,求调

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

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@lthdbatr
此快照首次捕获于
2024/03/07 23:13
2 年前
此快照最后确认于
2024/03/07 23:18
2 年前
查看原帖
CPP
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lowbit(x) x & -x
#define fup(x, l, r) for (int x = (l), eNd = (r); x <= eNd; ++x)
#define fdw(x, r, l) for (int x = (r), eNd = (l); x >= eNd; --x)
typedef long long ll;
typedef unsigned long long LL;
typedef pair<int, int> PII;

struct fastread
{
    template <typename T>
    fastread &operator>>(T &x)
    {
        x = 0;
        bool flg = false;
        char c = getchar();
        while (c < '0' || c > '9')
            flg |= (c == '-'), c = getchar();
        while (c >= '0' && c <= '9')
            x = (x << 3) + (x << 1) + c - '0', c = getchar();
        if (flg)
            x = -x;
        return *this;
    }
    template <typename T>
    fastread &operator>>(vector<T> &x)
    {
        for (auto it = x.begin(); it != x.end(); ++it)
            (*this) >> *it;
        return *this;
    }
} fin;

struct fastwrite
{
    template <typename T>
    fastwrite &operator<<(T x)
    {
        if (x < 0)
            x = -x, putchar('-');
        static int buf[35];
        int top = 0;
        do
            buf[top++] = x % 10, x /= 10;
        while (x);
        while (top)
            putchar(buf[--top] + '0');
        return *this;
    }
    fastwrite &operator<<(char x)
    {
        putchar(x);
        return *this;
    }
    template <typename T>
    fastwrite &operator<<(vector<T> x)
    {
        for (auto it = x.begin(); it != x.end(); ++it)
            (*this) << *it, putchar(' ');
        putchar('\n');
        return *this;
    }
} fout;

const int N = 1e6 + 10;
const int P = 998244353;

int n, m;
int a[N], c[N];
struct node
{
    int l, r;
    int sum;
    int lz;
} tr[N << 2];
struct tree
{
    void pushup(int rt)
    {
        tr[rt].sum = tr[ls].sum + tr[rs].sum;
    }
    void pushdown(int rt)
    {
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        tr[ls].sum += tr[rt].lz * (mid - tr[rt].l + 1);
        tr[rs].sum += tr[rt].lz * (tr[rt].r - mid);
        tr[ls].lz += tr[rt].lz;
        tr[rs].lz += tr[rt].lz;
        tr[rt].lz = 0;
    }
    void build(int rt, int l, int r)
    {
        tr[rt].lz = 0;
        tr[rt].l = l, tr[rt].r = r;
        if (l == r)
        {
            tr[rt].sum = c[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(rt);
    }
    void update(int rt, int l, int r, int v)
    {
        if (tr[rt].l >= l && tr[rt].r <= r)
        {
            tr[rt].sum += v * (tr[rt].r - tr[rt].l + 1);
            tr[rt].lz += v;
            return;
        }
        pushdown(rt);
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if (l <= mid)
            update(ls, l, r, v);
        if (r > mid)
            update(rs, l, r, v);
        pushup(rt);
    }
    int query(int rt, int l, int r)
    {
        if (tr[rt].l >= l && tr[rt].r <= r)
        {
            return tr[rt].sum;
        }
        pushdown(rt);
        int ans = 0;
        int mid = (tr[rt].l + tr[rt].r) >> 1;
        if (l <= mid)
            ans += query(ls, l, r);
        if (r > mid)
            ans += query(rs, l, r);
        return ans;
    }
} T;
main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fin >> n >> m;
    fup(i, 1, n) fin >> a[i];
    fup(i, 1, n) c[i] = c[i] - c[i - 1];
    // fup(i, 1, n) fout << c[i] << ' ';
    T.build(1, 1, n);
    while (m--)
    {
        int op, l, r, k, d, p;
        fin >> op;
        if (op == 1)
        {
            fin >> l >> r >> k >> d;
            T.update(1, l, l, k);
            if (l + 1 <= r)
                T.update(1, l + 1, r, d);
            if (r < n)
                T.update(1, r + 1, r + 1, -(k + d * (r - l)));
        }
        if (op == 2)
        {
            fin >> p;
            fout << T.query(1, 1, p) << '\n';
        }
    }
    return 0;
}

回复

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

正在加载回复...