分析:
分别维护两个值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;
}
}
}