E/F 小红出牌

思路

题解里都是思维，给一个硬维护的做法。

使用两个multiset，分别是L和R，分别维护每个顺子的左端点和右端点，然后考虑从左到右维护每一张纸牌所在的位置。

• 最好的情况下肯定是这一张纸牌把另外两堆的纸牌合并在一起，假设此时牌大小为 x ，那么就是要找到一个右端点为 x-1 且左端点为 x+1 的两个顺子，然后合并，在multiset里快速查询即可。

• 次好的情况就是将 x 加入到其中一个数字种，使得顺子数不增多，即在 L 里找 x-1 是否存在或者在R里 x+1 是否存在，如果存在，则加进去，同时记得修改端点。

• 最坏就是单独成一组，那么就在L和R里面都加入 x 形成新的左右端点即可。

每一次答案就是 L 或者 R 的大小。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
    int n;
    cin >> n;
    multiset<int> L, R;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        auto p1 = L.lower_bound(x + 1);
        auto p2 = R.lower_bound(x - 1);
        auto p3 = R.lower_bound(x - 1);
        auto p4 = L.lower_bound(x + 1);
        if (p3 != R.end() && p4 != L.end() && *p3 == x - 1 && *p4 == x + 1) {
            R.erase(p3);
            L.erase(p4);
        } else if (p1 != L.end() && *p1 == x + 1) {
            L.erase(p1);
            L.insert(x);
        } else if (p2 != R.end() && *p2 == x - 1) {
            R.erase(p2);
            R.insert(x);
        } else {
            L.insert(x);
            R.insert(x);
        }
        cout << L.size() << ' ';
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}