代码:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 5;
const int M = 1e7;
int m;
struct Val_Segment_Tree{
int tree[N] = {0}, top = 1;
int lch[N] = {0}, rch[N] = {0};
void pushup(int node){
tree[node] = tree[lch[node]] + tree[rch[node]];
}
void insert(int node, int lt, int rt, int x, int val){
if(!node){
node = ++top;
}
if(x < lt || x > rt){
return ;
}
if(lt == rt && lt == x){
tree[node] += val;
return ;
}
int mid = lt + rt >> 1;
insert(lch[node], lt, mid, x, val);
insert(rch[node], mid + 1, rt, x, val);
pushup(node);
}
int rank(int node, int lt, int rt, int x){
if(lt == rt){
return lt - M;
}
int mid = lt + rt >> 1;
if(x <= tree[lch[node]]){
return rank(lch[node], lt, mid, x);
}
else{
return rank(rch[node], mid + 1, rt, x - tree[lch[node]]);
}
}
int query1(int node, int lt, int rt, int x){
if(lt == rt){
return tree[node];
}
int mid = lt + rt >> 1;
if(x <= mid){
return query1(lch[node], lt, mid, x);
}
else{
return tree[lch[node]] + query1(rch[node], mid + 1, rt, x);
}
}
int query2(int node, int lt, int rt, int x){
if(lt == rt){
return 1;
}
int mid = lt + rt >> 1;
if(x <= mid){
return query2(lch[node], lt, mid, x);
}
else{
return tree[lch[node]] + query2(rch[node], mid + 1, rt, x);
}
}
}t;
signed main(){
cin >> m;
while(m--){
int op;
cin >> op;
if(op == 1){
int x;
cin >> x;
t.insert(1, 1, 2 * M, x + M, 1);
}
else if(op == 2){
int x;
cin >> x;
t.insert(1, 1, 2 * M, x + M, -1);
}
else if(op == 3){
int x;
cin >> x;
cout << t.query2(1, 1, 2 * M, x + M) << endl;
}
else if(op == 4){
int x;
cin >> x;
cout << x << endl;
cout << t.rank(1, 1, 2 * M, x) << endl;
}
else if(op == 5){
int x;
cin >> x;
cout << t.rank(1, 1, 2 * M, t.query2(1, 1, 2 * M, x + M) - 1) << endl;
}
else{
int x;
cin >> x;
cout << t.rank(1, 1, 2 * M, t.query1(1, 1, 2 * M, x + M) + 1) << endl;
}
}
return 0;
}