link

submission

题意： $Q$ 次操作，维护一个初始为空的序列。

+ x pos 在 $pos$ 后插入 $x$

? l r 查询最小值

我用的块状数组。求调 qwq

#include <bits/stdc++.h>
#ifdef LOCAL
#include <oi_debug/debug.hpp>
#endif
using namespace std;
#define int long long
signed Main();
signed main() {
#ifndef LOCAL
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);
#endif
    srand(time(0));
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.setf(ios::fixed), cout.precision(20);
    unsigned long long T = 1LL;
    /*T=read(); OR cin>>T;*/ while (T--)
        Main();
    return 0;
}
int SIZE = 1;
const int BLOCK = 450;
struct node {
    int nxt;
    int mn;
    int size;
    int a[BLOCK * 2 + 5];
    void pb(int x) { a[size++] = x; }
    node() {
        size = 0;
        nxt = -1;
        mn = INT_MAX;
        memset(a, 0, sizeof(a));
    }

} p[200500 / BLOCK + 5];
void Print() {
    // int tmp = 0;
    // for (int now = 0; now != -1; now = p[now].nxt) {
    //     cout << "# " << now << " nxt=" << p[now].nxt << " sz=" << p[now].size << " mn=" << p[now].mn
    //          << endl;
    //     for (int i = 0; i < p[now].size; ++i) {
    //         cout << p[now].a[i] << " ";
    //     }
    //     cout << endl;
    // }
}
void split(int P) {
    // cout << "Before Split()" << endl;
    Print();
    p[SIZE].size = BLOCK;
    p[SIZE].nxt = p[P].nxt;
    p[P].nxt = SIZE;
    for (int i = p[P].size - BLOCK; i < p[P].size; ++i) {
        p[SIZE].a[i - p[P].size + BLOCK] = p[P].a[i];
        p[P].a[i] = 0;
    }
    p[P].size -= BLOCK;
    int tmp = INT_MAX;
    for (int i = (p == 0) ? 1 : 0; i < p[P].size; ++i) {
        tmp = min(tmp, p[P].a[i]);
    }
    p[P].mn = tmp;
    tmp = INT_MAX;
    for (int i = 0; i < p[SIZE].size; ++i) {
        tmp = min(tmp, p[SIZE].a[i]);
    }
    p[SIZE].mn = tmp;
    ++SIZE;
    // cout << "After Split()" << endl;
}
void Insertb(int P, int x, int pos) {
    // cout << "InsertB(" << P << ", " << x << ", " << pos << ")" << endl;
    for (int i = p[P].size - 1; i >= pos + 1; --i) {
        p[P].a[i + 1] = p[P].a[i];
    }
    p[P].a[pos + 1] = x;
    p[P].mn = min(p[P].mn, x);
    if (++p[P].size >= BLOCK * 2) {
        split(P);
    }
}
int Query(int l, int r) {
    int tmp = 0;
    int ans = INT_MAX;
    for (int now = 0; now != -1; now = p[now].nxt) {
        int bl = tmp;
        int br = bl + p[now].size - 1;
        // cout << bl << " " << br << endl;
        tmp = br + 1;
        if (bl > r || br < l)
            continue;

        if (l <= bl && br <= r) {
            ans = min(ans, p[now].mn);
        } else if (br >= r) {
            for (int i = max(0ll, l - bl); i <= r - bl; ++i) {
                ans = min(ans, p[now].a[i]);
            }
        } else if (bl <= l) {
            for (int i = l - bl; i <= min(r - bl, p[now].size - 1); ++i) {
                ans = min(ans, p[now].a[i]);
            }
            break;
        }
    }
    return ans;
}
void Insert(int x, int pos) {
    int tmp = 0;
    for (int now = 0; now != -1; now = p[now].nxt) {
        int bl = tmp;
        int br = bl + p[now].size - 1;
        tmp = br + 1;
        // cout << bl << " " << br << endl;
        if (pos >= bl && pos <= br) {
            Insertb(now, x, pos - bl);
            return;
        }
    }
}
signed Main() {
    int Q;
    cin >> Q;
    Insertb(0, 0, 0);
    p[0].mn = INT_MAX;
    Print();
    while (Q--) {
        char op;
        cin >> op;
        int x;
        if (op == '+') {
            int x, pos;
            cin >> pos >> x;
            Insert(x, pos);
        } else {
            int l, r;
            cin >> l >> r;
            cout << Query(l, r) << endl;
        }
        Print();
    }
    return 0;
}