treap_RMQ

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <iomanip>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <limits.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(),(x).end()
#define pii pair<int, int>
#define sz(x) (int)x.size()

struct Node {
//val - значение в вершине, y - рандомный приоритет,
//size - размер обоих поддеревьев + 1 (сама вершина),
//min - минимум в вершине и обоих её поддеревьях
    int val, y, size, min;
    Node* left; Node* right;
    Node(int v) {
        this->val = this->min = v;
        this->size = 1;
        this->y = (rand() << 15) + rand();
//сдвиг делаю, потому что rand() до 32767, а надо, чтобы было поменьше одинаковых приоритетов
        this->left = this->right = NULL;
    }
};

//если указатель нулевой (NULL), то программа упадёт, если пытаться внутри него к чему-то обратиться
//поэтому случай нулевого указателя в ДД всегда разбирается отдельно и в начале

int get_min(Node* v) { return v == NULL ? INT_MAX : v->min; }

int get_size(Node* v) { return v == NULL ? 0 : v->size; }

//после сплитов и мерджей могли измениться дети => надо обновить информацию об их родителе
void update(Node* v) {
    if (v == NULL) return;
    v->size = get_size(v->left) + get_size(v->right) + 1;
    v->min = min(v->val, min(get_min(v->left), get_min(v->right)));
}

//сливает два дерева
Node* merge(Node* f, Node* s) {
    if (f == NULL) return s;
    if (s == NULL) return f;
//если f будет вершиной итогового дерева, то так как оно стоит слева от s
//(потому что на merge мы всегда вводим сначала дерево, которое стоит слева, а потом справа)
//его левый ребенок никак не изменится, а правый будет сливаться с s - это и делаем
    if (f->y > s->y) {
        f->right = merge(f->right, s);
        update(f);
        return f;
    }
//аналогично, если s оказалось вершиной итогового дерева, то его правый сын никак не
//изменится, а левый придётся сливать с f - это и делаем
    else {
        s->left = merge(f, s->left);
        update(s);
        return s;
    }
}

//здесь размышляем как "отрезать первые k элементов",
//тогда первый элемент пары - вершина ДД из первых k элементов,
//второй - вершина ДД с оставшимися элементами
pair<Node*, Node*> split_kth(Node* v, int k) {
    if (v == NULL) return { NULL, NULL };
//если в левом сыне не меньше k элементов, то именно его придётся резать, а
//правый сын и изначальная вершина останутся нетронутыми.
//когда мы разрезали левого ребёнка, надо прицепить к изначальной вершине тот обрубок,
//который остался после k элементов
    if (k <= get_size(v->left)) {
        auto res = split_kth(v->left, k);
        v->left = res.second;
        update(v);
        return { res.first, v };
    }
//те же размышления (я заебался писать просто уже немного)
    else {
        auto res = split_kth(v->right, k - get_size(v->left) - 1);
        v->right = res.first;
        update(v);
        return { v, res.second };
    }
}

//обрубили первые i элементов, присобачили посередине новый элемент и слили всё обратно
Node* insert(Node* v, int i, int x) {
    Node* elem = new Node(x);
    auto res = split_kth(v, i);
    return merge(res.first, merge(elem, res.second));
}

//обрубили кусок [l...r] (сначала отхерачили первые l-1, потом от второго куска ещё r-l+1)
//на этом куске в вершине уже будет храниться минимум (потому что в сплитах и мерджах мы делали обновления)
//запомнили ответ, соединили всё обратно и вернули ответ
int get_min(Node* v, int l, int r) {
    auto res1 = split_kth(v, l - 1);
    auto res2 = split_kth(res1.second, r - l + 1);
    int ans = res2.first->min;
    merge(res1.first, merge(res2.first, res2.second));
    return ans;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    Node* root = NULL;

    for (int i = 0; i < n; ++i) {
        char x;
        cin >> x;
        if (x == '+') {
            int i, x;
            cin >> i >> x;
            root = insert(root, i, x);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << get_min(root, l, r) << "\n";
        }
    }

    return 0;
}