4878. 维护数组

维护数组

分析：

分别维护两个值sum1, sum2，其他套线段树板子

实现：

struct Node
{
    int l, r;
    int minv;
    int sum1, sum2;
} tr[N << 2];
void pushup(Node &u, Node &l, Node &r)
{
    u.minv = min(l.minv, r.minv);
    u.sum1 = l.sum1 + r.sum1, u.sum2 = l.sum2 + r.sum2;
}
void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r)
{
    if (l == r)
        tr[u] = {l, l, 0, 0, 0};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(Lson), build(Rson);
        pushup(u);
    }
}
void modify(int u, int pos, int k)
{
    if (tr[u].l == pos && tr[u].r == pos)
    {
        tr[u].minv += k;
        tr[u].sum1 = min(tr[u].minv, b);
        tr[u].sum2 = min(tr[u].minv, a);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (pos <= mid)
            modify(u << 1, pos, k);
        else
            modify(u << 1 | 1, pos, k);
        pushup(u);
    }
}
int query(int u, int l, int r, int flag)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        if (flag == 1)
            return tr[u].sum2;
        else
            return tr[u].sum1;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = 0;
        if (l <= mid)
            res = query(u << 1, l, r, flag);
        if (r > mid)
            res += query(u << 1 | 1, l, r, flag);
        return res;
    }
}
void solve()
{
    cin >> n >> k >> a >> b >> q;
    build(1, 1, n);
    while (q--)
    {
        int op, x, y, p;
        cin >> op;
        if (op == 1)
        {
            cin >> x >> y;
            modify(1, x, y);
        }
        else
        {
            cin >> p;
            cout << query(1, 1, p - 1, 2) + query(1, p + k, n, 1) << endl;
        }
    }
}