```cpp
#include<bits/stdc++.h>
using namespace std;
#define rg register
#define mian main
typedef long long ll;
namespace treap{
using namespace std;
class TreapNode {
public:
int LS, RS;//LeftSon, RightSon
int Value, DATA;//Value, Priority
int sz, cpy;//SonSize, Copies
};
#define pii pair< int, int >
#define mp make_pair
#define MTP_S seed.first
#define MOD_S seed.second
#define vt vector<TreapNode>
#define R resize
#define pb push_back
#define INF INT_MAX
#define elif else if
class Treap {
private:
int rand;pii seed;
vt t;
int tot,root;
int GetRand() {
return rand = (1ll * rand * MTP_S) % MOD_S;
}
public:
#define NN_ NewNode
#define New NN_
#define GR_ GetRand
#define GensoukyoRailway GR_ //(bushi
//---------------------- OPERATIONS
int NewNode(int Val) {
TreapNode node;
node.Value = Val;
node.DATA = GR_();
node.sz = 1;
node.cpy = 1;
node.LS = node.RS = 0;
t[++tot] = node;
return tot;
}
void Pushup(int ID) {
t[ID].sz = t[t[ID].LS].sz + t[t[ID].RS].sz + t[ID].cpy;
}
// void Build(){
void Build(){
root = New(-INF), t[root].RS = New(INF);
Pushup(root);
}
Treap(int size,int S, int mtp, int mod) {
t.R(size+118);
rand = S;
seed = mp(mtp, mod);
tot=0;
Build();
}
Treap(int size,int S, int mtp) {
t.R(size+118);
rand = S;
seed = mp(mtp, 19970219);
tot=0;
Build();
}
Treap(int size,int S) {
t.R(size+118);
rand = S;
seed = mp(19260817, 19970219);
tot=0;
Build();
}
Treap(int size) {
t.R(size+118);
rand = 3344521;
seed = mp(19260817, 19970219);
tot=0;
Build();
}
Treap() {
t.R(1e7+118);
rand = 3344521;
seed = mp(19260817, 19970219);
tot=0;
Build();
}
// }
void Rotate(int &ID, bool dir) {
int tmp = (dir ? t[ID].LS : t[ID].RS);
(dir ? t[ID].LS : t[ID].RS) = (dir ? t[tmp].RS : t[tmp].LS);
(dir ? t[tmp].RS : t[tmp].LS) = ID;
ID = tmp;
Pushup(dir ? t[ID].RS : t[ID].LS), Pushup(ID);
}
void Rotate(int &ID, int direc) {
bool dir = (direc ? 1 : 0);
Rotate(ID, dir);
}
void Rotate(int &ID, char d) {
bool dir = ((d > 'a') ? ((d == 'l') ? 0 : 1) : ((d == 'L') ? 0 : 1));
Rotate(ID, dir);
}
void Rotate(int &ID, const char *d) {
bool dir = ((d[0] > 'a') ? ((d[0] == 'l') ? 0 : 1) : ((d[0] == 'L') ? 0 : 1));
Rotate(ID, dir);
}
void Insert(int &ID, int Val) {
if(!ID) {
ID = New(Val);
return;
}
if(Val ^ t[ID].Value) {
bool dir = ((Val < t[ID].Value) ? 0 : 1);
Insert((dir ? t[ID].RS : t[ID].LS), Val);
if(t[ID].DATA < t[(dir ? t[ID].RS : t[ID].LS)].DATA) Rotate(ID, !dir);
} else { t[ID].cpy++; }
Pushup(ID);
}
void Insert(int Val) {
Insert(root, Val);
}
void Remove(int &ID, int Val) {
if(!ID) return ;
if(Val == t[ID].Value) {
if(t[ID].cpy > 1) {
t[ID].cpy--;
Pushup(ID);
}
else if(t[ID].LS || t[ID].RS) {
if(!t[ID].RS || (t[t[ID].LS].DATA > t[t[ID].RS].DATA)) {
Rotate(ID,1), Remove(t[ID].RS,Val);
} else { Rotate(ID,1), Remove(t[ID].LS,Val); }
Pushup(ID);
} else { ID = 0; }
return ;
}
(Val < t[ID].Value) ? Remove(t[ID].LS,Val) : Remove(t[ID].RS,Val);
Pushup(ID);
}
void Delete(int &ID, int Val) {
Remove(ID, Val);
}
void Remove(int Val) {
Remove(root, Val);
}
void Delete(int Val) {
Remove(root, Val);
}
//---------------------- FUNCTIONS
int Main_GRKN(int ID, int Val) {
if(!ID) return 0;
if(Val == t[ID].Value) return t[t[ID].LS].sz + 1;
elif(Val < t[ID].Value) return Main_GRKN(t[ID].LS, Val);
else return t[t[ID].LS].sz + t[ID].cpy + Main_GRKN(t[ID].RS,Val);
}
int GetRank_KnownNum(int ID, int Val) {
return Main_GRKN(ID, Val) - 1;
}
int GetRank(int ID, int Val) {
return Main_GRKN(ID, Val) - 1;
}
int GRKN(int ID, int Val) {
return Main_GRKN(ID, Val) - 1;
}
int GR(int ID, int Val) {
return Main_GRKN(ID, Val) - 1;
}
int GetRank_KnownNum(int Val) {
return Main_GRKN(root, Val) - 1;
}
int GetRank(int Val) {
return Main_GRKN(root, Val) - 1;
}
int GRKN(int Val) {
return Main_GRKN(root, Val) - 1;
}
int GR(int Val) {
return Main_GRKN(root, Val) - 1;
}
int Main_GNKR(int ID, int rk) {
if(!ID) return INF;
if(rk <= t[t[ID].LS].sz) return Main_GNKR(t[ID].LS, rk);
elif(rk <= t[t[ID].LS].sz + t[ID].cpy) return t[ID].Value;
else return Main_GNKR(t[ID].RS, rk - t[t[ID].LS].sz - t[ID].cpy);
}
int GetNum_KnownRank(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GetNum(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GNKR(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GNum(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GetNum_KnownRank(int rk) {
return Main_GNKR(root, rk + 1);
}
int GetNum(int rk) {
return Main_GNKR(root, rk + 1);
}
int GNKR(int rk) {
return Main_GNKR(root, rk + 1);
}
int GNum(int rk) {
return Main_GNKR(root, rk + 1);
}
int GetVal(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GVKR(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GV(int ID, int rk) {
return Main_GNKR(ID, rk + 1);
}
int GetVal(int rk) {
return Main_GNKR(root, rk + 1);
}
int GVKR(int rk) {
return Main_GNKR(root, rk + 1);
}
int GV(int rk) {
return Main_GNKR(root, rk + 1);
}
int Main_GP(int Val) {
int ID = root, PNum;
while(ID) {
if(t[ID].Value < Val) PNum = t[ID].Value, ID = t[ID].RS;
else ID = t[ID].LS;
}
return PNum;
}
int GetPreviousNum(int Val) {
return Main_GP(Val);
}
int GetLast(int Val) {
return Main_GP(Val);
}
int GetPre(int Val) {
return Main_GP(Val);
}
int GL(int Val) {
return Main_GP(Val);
}
int GP(int Val) {
return Main_GP(Val);
}
int Main_GN(int Val) {
int ID = root, NNum;
while(ID) {
if(t[ID].Value > Val) NNum = t[ID].Value, ID = t[ID].LS;
else ID = t[ID].RS;
}
return NNum;
}
int GetFollowingNum(int Val) {
return Main_GN(Val);
}
int GetFol(int Val) {
return Main_GN(Val);
}
int GetNext(int Val) {
return Main_GN(Val);
}
int GF(int Val) {
return Main_GN(Val);
}
int GN(int Val) {
return Main_GN(Val);
}
};
}using namespace treap;
inline void read(int &x) {
scanf("%d", &x);
}
inline void read(int &x, int &y) {
scanf("%d%d", &x, &y);
}
inline void write(int x) {
printf("%d", x);
}
mian() {
Treap T(1e5);
int n, x, opt;
read(n);
while(n--) {
read(opt,x);
if(opt == 1) {
T.Insert(x);
} elif(opt == 2) {
T.Remove(x);
} elif(opt == 3) {
printf("%d\n", T.GR(x));
} elif(opt == 4) {
printf("%d\n", T.GV(x));
} elif(opt == 5) {
printf("%d\n", T.GP(x));
} else {
printf("%d\n", T.GN(x));
}
}
#if WIN32
system("PAUSE>NUL");
#endif
}
```
by Bythe @ 2021-05-03 09:10:30