OBI-solutions/2015/phase2/fila.cpp

/* Problem URL: https://olimpiada.ic.unicamp.br/pratique/p2/2015/f2/fila/ */

#include <bits/stdc++.h>

using namespace std;

#define V vector

#define rmin(a, b) a = min(a, b)
#define rmax(a, b) a = max(a, b)

#define rep(i, lim) for (size_t i = 0; i < (lim); i++)
#define nrep(i, s, lim) for (size_t i = s; i < (lim); i++)

#define repv(i, v) for (auto &i : (v))
#define fillv(v) for (auto &itr_ : (v)) { cin >> itr_; }
#define sortv(v) sort(v.begin(), v.end())
#define all(v) (v).begin(), (v).end()

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;

using ll = long long;

using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vvvvl = vector<vvvl>;

template<class v>
auto operator<<(ostream &os, const vector<v> &vec)->ostream& {
    os << vec[0];
    for (size_t i = 1; i < vec.size(); i++) {
        os << ' ' << vec[i];
    }
    os << '\n';
    return os;
}

template<class v>
auto operator>>(istream &is, vector<v> &vec)->istream& {
    for (auto &i : vec) {
        is >> i;
    }
    return is;
}

template<class v>
auto operator<<(ostream &os, const vector<vector<v>> &vec)->ostream& {
    for (auto &i : vec) {
        os << i[0];
        for (size_t j = 1; j < i.size(); j++) {
            os << ' ' << i[j];
        }
        os << '\n';
    }
    return os;
}

template<class v>
auto operator>>(istream  &is, vector<vector<v>> &vec)->istream& {
    for (auto &i : vec) {
        for (auto &j : i) {
            is >> j;
        }
    }
    return is;
}

#define int ll

struct insertion {
    int pos;
    int val;

    insertion(int pos, int val): pos(pos),
                                 val(val) {}
};

struct query {
    int type;
    int pos;
    ll val;

    query() : type(0), pos(0), val(0) {}
    query(int type, int pos, ll val): type(type),
                                       pos(pos),
                                       val(val) {}
};

vl segtree;
vl bit;

ll search(int n, int l, int r, int lim, int v)
{
    if (segtree[n] <= v || l >= lim) {
        return 0;
    }

    if (l == r) {
        return l;
    }

    int mid = (l + r) / 2;
    ll ans = segtree[n * 2 + 1] > v ? search(n * 2 + 1, mid + 1, r, lim, v) : 0;
    return ans ?: search(n * 2, l, mid, lim, v);
}

void add(int i, int v = 1)
{
    for (; i < bit.size(); i += (i & -i)) {
        bit[i] += v;
    }
}

ll get(int v)
{
    ll ans = 0;
    for (int i = 31; i >= 0; i--) {
        ll tmp = (1 << i) + ans;
        if (tmp >= bit.size()) {
            continue;
        }

        if (bit[tmp] <= v) {
            v -= bit[tmp];
            ans = tmp;
        }
    }
    if (v == 0) return ans;
    return -1;
}

ll sum(int i)
{
    ll ans = 0;
    for (; i > 0; i -= i & -i) {
        ans += bit[i];
    }
    return ans;
}

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

    int n;
    cin >> n;
    vl queue(n);
    V<insertion> inserts;
    // cin >> queue;
    rep(i, n) {
        int val;
        cin >> val;
        inserts.emplace_back(i, val);
    }

    int q;
    cin >> q;
    V<query> queries(q + n);
    for (size_t i = 0; i < inserts.size(); i++) {
        queries[i] = query(0, inserts[i].pos, inserts[i].val);
    }

    size_t num = inserts.size();

    nrep(i, n, n + q) {
        int type, pos;
        ll value;
        cin >> type >> pos >> value;
        queries[i] = query(type, pos, value);
        if (type == 0) {
            num++;
        }
    }

    vl act(num, -1);
    bit.assign(queries.size() + 1, 0);
    for (size_t i = 1; i <= queries.size(); i++) {
        add(i);
    }

    for (auto itr = queries.rbegin(); itr != queries.rend(); itr++) {
        auto &[t, p, v] = *itr;

        if (t == 0) {
            p = get(p) + 1;

            add(p, -1);
            continue;
        }
        p = get(p - 1) + 1;
    }

    while (act.size() != 0 && __builtin_popcount(act.size()) != 1) {
        act.push_back(-1);
    }

    segtree.assign(act.size() * 2, -1);
    bit.assign(act.size() + 1, 0);

    for (auto [type, pos, value] : queries) {
        // cerr << bit;
        if (type == 0) {
            add(pos);

            act[pos - 1] = value;
            segtree[act.size() + pos - 1] = value;
            for (size_t i = (act.size() + pos - 1) / 2; i > 0; i /= 2) {
                segtree[i] = max(segtree[i * 2], segtree[i * 2 + 1]);
            }
            continue;
        }

        int ans = search(1, 1, act.size(), pos, act[pos - 1] + value);
        cout << sum(ans) << '\n';
    }
}