Balance Update Query

link

省选前写点简单题攒 rp。

显然每次选择，我们应该将所有物品从大到小排序，每次选择最大的 \(x\) 个。

也就是每次要求前 \(x\) 大的数的和，随手写个平衡树可以做到这一操作，但是我不会，这里选择权值线段树来存贮每个数的个数，用线段树上二分解决前 \(x\) 大的数的和。

注意离散化和数组大小。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 4e5 + 5;

int n, q;
int a[N], b[N];
struct oper {
	int op, x, y;
} Q[N];
vector<int> nums;

struct SegT {
	int l, r, siz;
	ll sum;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define siz(x) tr[x].siz
	#define sum(x) tr[x].sum 
} tr[N << 2];

void build(int l, int r, int x) {
	tr[x] = {l, r};
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, x * 2), build(mid + 1, r, x * 2 + 1);
}

void pushup(int x) {
	siz(x) = siz(x * 2) + siz(x * 2 + 1);
	sum(x) = sum(x * 2) + sum(x * 2 + 1);
}

void update(int x, int p, int v) {
	if (l(x) == r(x)) {
		siz(x) += v;
		sum(x) += 1ll * nums[p - 1] * v;
		return;
	}
	int mid = (l(x) + r(x)) / 2;
	if (p <= mid) update(x * 2, p, v);
	else update(x * 2 + 1, p, v);
	pushup(x);
}

ll query(int x, int k) {
	if (!k) return 0;
	if (l(x) == r(x)) {
		return 1ll * k * nums[l(x) - 1];
	}
	int mid = (l(x) + r(x)) / 2;
	if (siz(x * 2 + 1) >= k) return query(x * 2 + 1, k);
	else return sum(x * 2 + 1) + query(x * 2, k - siz(x * 2 + 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i ++) {
    	cin >> a[i] >> b[i];
    	nums.push_back(a[i]);
    }
    cin >> q;
    for (int i = 1; i <= q; i ++) {
    	int op, x, y = 0;
    	cin >> op >> x;
    	if (op == 1) {
    		cin >> y;
    		nums.push_back(y);
    	}
    	else if (op == 2) {
    		cin >> y;
    	}
    	Q[i] = (oper){op, x, y};
    }

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    build(1, (int)nums.size(), 1);

    for (int i = 1; i <= n; i ++) {
    	a[i] = lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() + 1;
    	update(1, a[i], b[i]);
    }
    for (int i = 1; i <= q; i ++) {
    	int op = Q[i].op, x = Q[i].x, y = Q[i].y;
    	if (op == 1) {
    		y = lower_bound(nums.begin(), nums.end(), y) - nums.begin() + 1;
    		update(1, a[x], -b[x]);
    		a[x] = y;
    		update(1, a[x], b[x]);
    	}
    	else if (op == 2) {
    		update(1, a[x], y - b[x]);
    		b[x] = y;
    	}
    	else {
    		if (siz(1) < x) {
    			cout << -1 << '\n';
    		}
    		else {
    			cout << query(1, x) << '\n';
    		}
    	}
    }
    return 0;
}