Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:268435456")
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <iomanip>
- #include <stack>
- #include <string>
- #include <set>
- #include <queue>
- #include <functional>
- #include <deque>
- #include <cmath>
- #include <sstream>
- #include <bitset>
- #define what_is(x) cerr << #x << " = " << x << endl;
- using namespace std;
- #define forn(i,n) for(int i = 0; i < n; i++)
- #define forr(i,n) for(int i = n-1; i >= 0; i++)
- #define ALL(x) x.begin(),x.end()
- #define mp make_pair
- #define sf(x,y) scanf("%" x,&y)
- #define pf(x,y) printf("%" x,y)
- #define sqr(x) (x)*(x)
- typedef long long int64;
- typedef long double ld;
- #define int int64
- typedef unsigned long long uint64;
- typedef pair<int, int> pii;
- typedef pair<int64, int64> pii64;
- typedef pair<double, double> pdd;
- typedef vector<int> vint;
- typedef vector<int64> vint64;
- typedef vector<double> vd;
- typedef vector<vint> vvint;
- template <typename T1, typename T2> istream& operator >> (istream& in, pair<T1, T2>& t) { return in >> t.first >> t.second; }
- template <typename T1, typename T2> ostream& operator << (ostream& out, pair<T1, T2>& t) { return out << t.first << " " << t.second << endl; }
- template <typename T> istream& operator >> (istream& in, vector<T>& t) { for (int i = 0; i < t.size(); i++) in >> t[i]; return in; }
- template <typename T> ostream& operator << (ostream& out, vector<T>& t) { for (int i = 0; i < t.size(); i++) out << t[i] << " "; return out; }
- struct ST {
- struct Item {
- Item *l = 0, *r = 0;
- int mn = 2e9;
- int cnt = 0;
- Item(int val, int cnt) : mn(val), cnt(cnt) {}
- Item() {}
- };
- Item* root = 0;
- vector<Item*> g;
- int get_mn(Item* it) {
- return it ? it->mn : 2e9;
- }
- int get_cnt(Item* it) {
- return it ? it->cnt : 0;
- }
- void upd(Item* it) {
- it->mn = min(get_mn(it->l), get_mn(it->r));
- it->cnt = get_cnt(it->l) + get_cnt(it->r);
- }
- Item* build(vint& ve, int l, int r) {
- if (l > r) return 0;
- if (l == r) {
- return new Item(ve[l], 1);
- }
- int m = (l + r) / 2;
- Item* it = new Item();
- it->l = build(ve, l, m);
- it->r = build(ve, m + 1, r);
- upd(it);
- return it;
- }
- void insert(int i, int val, Item* v) {
- if (v == 0) {
- v = new Item(val, 1); return;
- }
- if (v->l == 0 && v->r == 0) {
- v->r = new Item(v->mn, 1);
- v->l = new Item(val, 1);
- upd(v); return;
- }
- if (v->cnt - 1 >= i) {
- insert(i, val, v->l);
- }else insert(i - get_cnt(v->l), val, v->r);
- }
- void rebuild() {
- vint t; t.reserve(2e5); dfs(t, root);
- build(t, 0, t.size() - 1);
- }
- void dfs(vint& t, Item* v) {
- if (v == 0) return;
- if (v->l == 0 && v->r == 0) {
- t.push_back(v->mn);
- delete v;
- return;
- }
- dfs(t, v->l);
- dfs(t, v->r);
- }
- int mn(Item* v, int l, int r){
- if (r < 0) return 2e9;
- if (l <= 0 && get_cnt(v) - 1 <= r){
- return get_mn(v);
- }
- mn(v->l, l, r);
- mn(v->r, l - get_cnt(v->l), r - get_cnt(v->l));
- }
- };
- signed main()
- {
- freopen("abc.txt", "r", stdin);
- int n; cin >> n;
- ST tree;
- for(int i = 0;i < n; ++i) {
- char op; cin >> op;
- if(op == '+'){
- int i, x; cin >> i >> x;
- tree.insert(i, x, tree.root);
- } else {
- int i, j; cin >> i >> j; i--; j--;
- cout << tree.mn(tree.root, i, j) << endl;
- }
- if(i % 1000 == 0) tree.rebuild();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement