公式

D - Querying Multiset 解説 by en_translator


Define a sequence \((A_1,\ldots ,A_N)\) so that if the \(i\)-th operation is Operation \(2\), then \(A_i=X_i\), or otherwise \(0\). Then, the number written on each ball in the bag right before the \((K+1)\)-th operation is \(X_i+A_{i+1}+\cdots A_K\). Here, with the aid of the idea of cumulative sums, it can be expressed as \(X_i+(S_K-S_i)=(X_i-S_i)+S_K\), where \(S_i=A_1+\cdots A_i\). Here, \((A_i)\) and \((S_i)\) can be easily calculated by inspecting them in order.

Now, when we pick up the ball with the minimum number, \(S_K\) is independent of balls, so it is sufficient to pick up the ball with the minimum value of \(X_i-S_i\).
Therefore, for each Operation \(1\), we can assume that we put all ball with the value \(X_i-S_i\) written on it, rather than \(X_i\), so that we only have to consider Operation \(1\) and \(3\). (Do not forget to add \(S_K\) before outputting.)

This can be solved fast enough with a data structure like a priority queues, specifically in a total of \(O(Q\log Q)\) time. Therefore, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
	priority_queue<ll, vector<ll>, greater<ll> >pq;
	int q, p;
	ll x;
	ll sum = 0;
	cin >> q;
	rep(qq, q) {
		cin >> p;
		if (p == 1) {
			cin >> x;
			pq.push(x - sum);
		}
		else if (p == 2) {
			cin >> x;
			sum += x;
		}
		else if (p == 3) {
			x = pq.top();
			cout << x + sum << endl;
			pq.pop();
		}
	}
	return 0;
}

投稿日時:
最終更新: