#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <ctime>
#include <random>
#include <set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define PATH "D:\\QtProjects\\olymp\\"
template <class T> void mx(T& a, const T& b) { if (a < b) a = b; }
template <class T> void mn(T& a, const T& b) { if (a > b) a = b; }
typedef tree<int, null_type> TREE;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> TREE2;
struct item {
int key, prior;
item * l, * r;
item() { }
item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item * pitem;
void split (pitem t, int key, pitem & l, pitem & r) {
if (!t)
l = r = NULL;
else if (key < t->key)
split (t->l, key, l, t->l), r = t;
else
split (t->r, key, t->r, r), l = t;
}
void insert (pitem & t, pitem it) {
if (!t)
t = it;
else if (it->prior > t->prior)
split (t, it->key, it->l, it->r), t = it;
else
insert (it->key < t->key ? t->l : t->r, it);
}
void merge (pitem & t, pitem l, pitem r) {
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
merge (l->r, l->r, r), t = l;
else
merge (r->l, l, r->l), t = r;
}
void erase (pitem & t, int key) {
if (t->key == key)
merge (t, t->l, t->r);
else
erase (key < t->key ? t->l : t->r, key);
}
pitem unite (pitem l, pitem r) {
if (!l || !r) return l ? l : r;
if (l->prior < r->prior) swap (l, r);
pitem lt, rt;
split (r, l->key, lt, rt);
l->l = unite (l->l, lt);
l->r = unite (l->r, rt);
return l;
}
const int N = 1e6;
int rnds[N];
int main(){
//freopen(PATH"input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
TREE2 ss;
set<int> sset;
srand(clock());
for (int i = 0; i < N; ++i)
rnds[i] = (rand() << 15) + rand();
clock_t curt = clock();
for (int i = 0; i < N; ++i)
ss.insert(rnds[i]);
clock_t curt2 = clock();
cout << "inserttime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
curt = clock();
curt = clock();
for (int i = 0; i < N; ++i)
sset.insert(rnds[i]);
curt2 = clock();
cout << "inserttime set:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
cout << "sizes" << sset.size() << ' ' << ss.size() << endl;
curt = clock();
pitem rt = NULL;
for (int i = 0; i < N; ++i)
insert(rt, new item(rnds[i], (rand() << 15) & rand()));
curt2 = clock();
cout << "inserttime treap:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
curt = clock();
for (int i = 0; i < N; ++i)
rnds[i] = *ss.find_by_order(i);
curt2 = clock();
cout << "foundtime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
curt = clock();
int i = 0;
for (auto it = ss.begin(); it != ss.end(); ++it)
rnds[i++] = *it;
curt2 = clock();
cout << "gothroughtime:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
curt = clock();
i = 0;
for (auto it = sset.begin(); it != sset.end(); ++it)
rnds[i++] = *it;
curt2 = clock();
cout << "gothroughtime set:" << (double)(curt2 - curt) / CLOCKS_PER_SEC << endl;
for (int i = 1; i < N; ++i)
assert(rnds[i] >= rnds[i - 1]);
return 0;
}