Решение RMQ из тренировки на ДО

vector<int> f;
void f_inc(int i, int d)
{
    while (i < f.size())
    {
        f[i] += d;
        i = i | (i + 1);
    }
}
int f_get(int i)
{
    int sum = 0;
    while (i >= 0)
    {
        sum += f[i];
        i = (i & (i + 1)) - 1;
    }
    return sum;
}

int find_f_pos(int a)
{
    int i = 0;
    while ((1 << i) < f.size()) i++;
    int l = 0;
    while (i > 0)
    {
        i--;
        int m = l + (1 << i) - 1;
        if (m >= f.size())
            continue;
        if (f[m] < a)
        {
            a -= f[m];
            l = m + 1;
        }
    }
    return l;
}

vector<int> min_do;
void do_set(int i, int a, int d = 1, int lf = 0, int rf = f.size() - 1)
{
    if (lf == rf)
    {
        min_do[d] = a;
        return;
    }
    int m = (lf + rf) / 2;
    if (i <= m)
        do_set(i, a, d * 2, lf, m);
    else
        do_set(i, a, d * 2 + 1, m + 1, rf);
    min_do[d] = min(min_do[d * 2], min_do[d * 2 + 1]);
}
int do_get(int l, int r, int d = 1, int lf = 0, int rf = f.size() - 1)
{
    if (lf == l && rf == r)
    {
        return min_do[d];
    }
    int m = (lf + rf) / 2;
    if (r <= m)
        return do_get(l, r, d * 2, lf, m);
    if (l > m)
        return do_get(l, r, d * 2 + 1, m + 1, rf);
    return min(do_get(l, m, d * 2, lf, m), do_get(m + 1, r, d * 2 + 1, m + 1, rf));
}

int main() {
//#ifndef DEBUG
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);
//#endif
    ifstream fin("rmq.in");
    ofstream fout("rmq.out");
    int n;
    fin >> n;
    vector<pair<bool, pair<int, int>>> req(n);
    int sz = 0;
    for (auto&r:req)
    {
        char c;
        while ((c = fin.get()) < 43);
        fin >> r.second.first >> r.second.second;
        r.first = c == '?';
        sz += c == '+';
    }

    f.resize(sz, 0);
    for (int i = 0; i < sz; i++)
        f_inc(i, 1);
    for (int i = n - 1; i >= 0; i--)
    {
        if (req[i].first)
        {
            int p = find_f_pos(req[i].second.first);
            req[i].second.first = p;
            p = find_f_pos(req[i].second.second);
            req[i].second.second = p;
        }
        else
        {
            int p = find_f_pos(req[i].second.first + 1);
            req[i].second.first = p;
            f_inc(p, -1);
        }
    }

    min_do.resize(sz * 4, INT32_MAX);
    for (int i = 0; i < n; i++)
    {
        if (req[i].first)
        {
            int l = req[i].second.first;
            int r = req[i].second.second;
            fout << do_get(l, r) << '\n';
        }
        else
        {
            int p = req[i].second.first;
            f_inc(p, 1);
            do_set(p, req[i].second.second);
        }
    }
    fout.flush();
    return 0;
}