洛谷真题

**#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const double alpha = 0.75;
struct Node {int l, r, size, fact, val, exist;
} tr[maxn];
int cnt, root;
#define get tr[now]
#define getl tr[get.l]
#define getr tr[get.r]int newNode(int v) {int now = ++cnt;get.val = v;get.size = get.fact = get.exist = 1;return now;
}bool isBanlance(int now) {// 左右子树不平衡 or 删除的节点太多if (get.size * alpha < max(getl.size, getr.size) or get.size * 0.7 > get.fact) {return false;}return true;
}void reset(int now) {get.l = get.r = 0;get.size = get.fact = get.exist = 1;
}vector<int> v;void collect(int now) {if (!now) return;collect(get.l);if (get.exist) {v.push_back(now);}collect(get.r);
}void lift(int &now, int l, int r) {//if (!now) return; sb 加了这一行代码if (l == r) {now = v[l];reset(now);return;}int m = (l + r) >> 1;while (m > l and tr[v[m]].val == tr[v[m - 1]].val) m--;now = v[m];if (m > l) lift(get.l, l, m - 1);else {get.l = 0;}lift(get.r, m + 1, r);get.size = getl.size + getr.size + 1;get.fact = get.size;get.exist = 1;
}void update(int now, int end) {if (!now) return;if (tr[end].val < get.val) {update(get.l, end);}  else {update(get.r, end);}get.size = getl.size + getr.size + 1;
}void rebuild(int& now) {if (!now) return;v.clear();collect(now);if (v.empty()) {now = 0;return;}lift(now, 0, v.size() - 1);update(root, now);
}void check(int& now, int end) {if (now == end) return;if (!isBanlance(now)) {rebuild(now);return;}if (tr[end].val < get.val) {check(get.l, end);} else {check(get.r, end);}
}void ins(int& now, int v) {if (!now) {now = newNode(v);check(root, now);return;}get.size++;get.fact++;if (v < get.val) {ins(get.l, v);} else {ins(get.r, v);}
}void del(int& now, int v) {if (!now) {return;}get.fact--;if (get.exist and get.val == v) {get.exist = 0;check(root, now);return;}if (v < get.val) {del(get.l, v);} else {del(get.r, v);}
}int getrank(int val) {int now = root, rank = 1;while (now) {if (val <= get.val) {now = get.l;} else {rank += getl.fact + get.exist;now = get.r;}}return rank;
}int getnum(int rank) {int now = root;while (now) {if (get.exist and getl.fact + 1 == rank) {break;}if (getl.fact >= rank) {now = get.l;} else {rank -= getl.fact + get.exist;now = get.r;}}return get.val;
}int main() {int t, opt, x;cin >> t;while (t--) {cin >> opt >> x;switch(opt){case 1:ins(root,x);break;case 2:del(root,x);break;case 3:cout << getrank(x) << endl;break;case 4:cout << getnum(x) << endl;break;case 5:cout << getnum(getrank(x)-1) << endl;break;case 6:cout << getnum(getrank(x+1)) << endl;break;}}
}