线段树上二分入门题。
考虑一个贪心:每次询问按 \(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;
}
- Beginner AtCoder Balance Contest Updatebeginner atcoder balance contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 332 beginner atcoder contest 334 beginner atcoder contest 310