Subtask 2

Để giảm độ phức tap truy vấn ~2~, ta có thể duy trì một biến ~d~ để lưu tổng các giá trị ~v~ cần thay đổi thay vì cập nhật cho từng phần tử trong hàng. Khi cần thêm phần tử ~x~ mới, nhận xét rằng các phần tử cũ sẽ chênh lệch giá trị với phần tử mới một khoảng đúng ~d~, nên ta chỉ cần thêm ~x - d~ vào trong hàng hiện tại.

Lưu ý rằng trước khi in kết quả cuối cùng ta cần cộng lại cho mỗi phần tử đúng ~d~ giá trị, vì giá trị thật của các phần tử trong hàng đang lệch một khoảng ~d~ giá trị.

Độ phức tạp: ~\mathcal{O}(q)~.

Subtask 3

Để có thể xoá nhanh các phần tử trong truy vấn ~3~ ta có thể sử dụng cấu trúc dữ liệu multiset trong C++, tuy nhiên vì multiset sẽ tự động sắp xếp lại các phần tử theo giá trị nên vị trí các phần tử sau khi thực hiện xong toàn bộ truy vấn có thể bị xáo trộn.

Ta sẽ duy trì thêm một biến ~id~ cho biết vị trí của phần tử cuối cùng, khi thêm phần tử ta có thể cập nhật ~id~ lên 1 rồi gắn ~id~ hiện tại cho phần tử mới thêm. Điều này có thể thực hiện bằng cách duy trì một multiset các cặp phần tử, mỗi cặp gồm giá trị và vị trí khi thêm. Nhận xét rằng khi thêm một phần tử mới vào hàng thì ta luôn thêm vào sau cùng, nên vị trí của phần tử mới thêm luôn lớn hơn vị trí của các phần tử trước. Do đó, dù ta có xoá các phần tử khác như thế nào thì độ lớn tương quan của các vị trí trong multiset sẽ không đổi.

Để lấy được thứ tự đúng của các phần tử, sau khi thực hiện hết các truy vấn ta có thể đưa các cặp phần tử trong multiset vào một mảng, rồi sắp xếp lại mảng đó dựa trên vị trí.

Độ phức tạp: ~\mathcal{O}(q \cdot \log{2}{q})~.

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int q;
multiset<pair<int, int>> S;
void ReadInput()
{
    cin >> q;
}
void Solve()
{
    int cur = 0;
    int cnt = 0;
    while(q-- > 0)
    {
        int type, x;
        cin >> type >> x;
        if(type == 1) S.insert({x - cur, ++cnt});
        else if(type == 2) cur += x;
        else
        {
            while(true)
            {
                auto it = S.lower_bound({x - cur, 0});
                if(it == S.end() || it->fi > x - cur) break;
                S.erase(it);
            }
        }
    }
    vector<pair<int, int>> vc;
    for(auto v : S) vc.pb({v.se, v.fi});
    sort(vc.begin(), vc.end());
    cout << vc.size() << '\n';
    for(auto v : vc)
        cout << v.se + cur << " ";

}
#define taskname ""
int32_t main()
{
    if (fopen(taskname ".inp", "r"))
    {
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
   // cin >> T;
    for(int itest=1; itest<=T; itest++)
    {
        ReadInput();
        Solve();
    }
}