线段树上二分入门题。
考虑一个贪心：每次询问按 \(a_i\) 从大到小选。正确性显然。
考虑动态开点线段树，每个结点 \(a_i \in [l, r]\) 存 \(\sum\limits_{a_i \in [l, r]} b_i\) 和 \(\sum\limits_{a_i \in [l, r]} a_i b_i\)。线段树上二分找到第一个 \(\sum\limits_{i = y}^{\infty} b_i > x\) 的 \(p\)，那么 \(p + 1 \sim \infty\) 全选，\(p\) 选的数量根据还能选多少数而定。
时间复杂度 \(O((n + q) \log V)\)。
code
// Problem: G - Balance Update Query
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 New Year (AtCoder Beginner Contest 287)
// URL: https://atcoder.jp/contests/abc287/tasks/abc287_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
const int N = 1000000000;
int n, m, a[maxn], b[maxn];
ll sum[maxn << 7];
int rt, ntot, ls[maxn << 7], rs[maxn << 7], cnt[maxn << 7];
void update(int &rt, int l, int r, int x, ll y) {
if (!rt) {
rt = ++ntot;
}
cnt[rt] += y;
sum[rt] += x * y;
if (l == r) {
return;
}
int mid = (l + r) >> 1;
if (x <= mid) {
update(ls[rt], l, mid, x, y);
} else {
update(rs[rt], mid + 1, r, x, y);
}
}
int querycnt(int rt, int l, int r, int ql, int qr) {
if (ql > qr || !rt) {
return 0;
}
if (ql <= l && r <= qr) {
return cnt[rt];
}
int mid = (l + r) >> 1, res = 0;
if (ql <= mid) {
res += querycnt(ls[rt], l, mid, ql, qr);
}
if (qr > mid) {
res += querycnt(rs[rt], mid + 1, r, ql, qr);
}
return res;
}
ll querysum(int rt, int l, int r, int ql, int qr) {
if (ql > qr || !rt) {
return 0;
}
if (ql <= l && r <= qr) {
return sum[rt];
}
int mid = (l + r) >> 1;
ll res = 0;
if (ql <= mid) {
res += querysum(ls[rt], l, mid, ql, qr);
}
if (qr > mid) {
res += querysum(rs[rt], mid + 1, r, ql, qr);
}
return res;
}
int find(int rt, int l, int r, int x) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
if (cnt[rs[rt]] > x) {
return find(rs[rt], mid + 1, r, x);
} else {
return find(ls[rt], l, mid, x - cnt[rs[rt]]);
}
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &a[i], &b[i]);
update(rt, 0, N, a[i], b[i]);
}
scanf("%d", &m);
while (m--) {
int op, x, y;
scanf("%d%d", &op, &x);
if (op == 1) {
scanf("%d", &y);
update(rt, 0, N, a[x], -b[x]);
a[x] = y;
update(rt, 0, N, a[x], b[x]);
} else if (op == 2) {
scanf("%d", &y);
update(rt, 0, N, a[x], y - b[x]);
b[x] = y;
} else {
int t = querycnt(rt, 0, N, 0, N);
if (t < x) {
puts("-1");
continue;
}
if (t == x) {
printf("%lld\n", querysum(rt, 0, N, 0, N));
continue;
}
int pos = find(rt, 0, N, x);
ll p = querycnt(rt, 0, N, pos + 1, N), q = querysum(rt, 0, N, pos + 1, N);
printf("%lld\n", q + (x - p) * pos);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}