大富翁游戏

有n个人在玩大富翁游戏，每个人初始都有100块钱。

随着游戏轮次的进行，每个人拥有的资金会有所变动。每过一些轮次，大家就会想要知道现在场上拥有最多资金的人的资金数和拥有最少资金的人的资金数。

你需要在每次询问的时候给出答案。

输入格式

第一行两个数n,m，代表一共有n个人和总计m次资金变动或询问。

接下来m行，每行读入1个或3个数:

• 如果第一个数为1，则表示资金变动，你需要再读入两个数p和x，表示第p个人的资金增加了x(可能为负)；

• 如果第一个数为2，则表示询问，你需要输出当前的最大和最小资金数。

输出格式

需要对每一次询问，一行输出两个数表示答案。

数据规模

对于100%的数据，保证1≤n,m≤100000,1≤p≤n,−100≤x≤100

3 3
1 1 50
1 3 -100
2

Output:

150 0

Solution:

#include 
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector a(n, 100);
    priority_queue> q1; // qbig;
    priority_queue, vector>, greater>> q2; // qsmall;
    for (int i = 0; i < n; ++i) {
        q1.push({100, i});
        q2.push({100, i});
    }
    for (int i = 0; i < m; ++i) {
        int op;
        cin >> op;
        if (op == 1) {
            int p, x;
            cin >> p >> x;
            p--;
            a[p] += x;
            if (p == q1.top().second) {
                q1.pop();
                q1.push({a[p], p});
                while (q1.top().first != a[q1.top().second]) {
                    q1.push({a[q1.top().second], q1.top().second});
                    q1.pop();
                }
            } else {
                q1.push({a[p], p});
            }
            if (p == q2.top().second) {
                q2.pop();
                q2.push({a[p], p});
                while (q2.top().first != a[q2.top().second]) {
                    q2.push({a[q2.top().second], q2.top().second});
                    q2.pop();
                }
            } else {
                q2.push({a[p], p});
            }
        } else {
            // cout << *max_element(a.begin(), a.end()) << ' ' << *min_element(a.begin(), a.end()) << 'n';
            cout << q1.top().first << ' ' << q2.top().first << 'n'; // 用堆将查询的 n 优化为 log(n)
        }
    }
    return 0;
}