Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <random>
- using namespace std;
- struct vertice{
- int x;
- int y;
- int c;
- vertice* l;
- vertice* r;
- vertice (){
- x = -1;
- y = rand();
- c = 0;
- l = NULL;
- r = NULL;
- }
- vertice (int a){
- x = -1;
- y = rand();
- c = a;
- l = NULL;
- r = NULL;
- }
- };
- vertice* root = NULL;
- int c(vertice* v){
- if (v == NULL){
- return 0;
- }
- return v -> c;
- }
- void change(vertice* v){
- if (v == NULL){
- return;
- }
- v -> c = c(v -> l) + c(v -> r);
- }
- pair < vertice*, vertice* > split (vertice* now, int a){
- if (now == NULL){
- return {NULL, NULL};
- }
- if (c(now -> l) < a){
- auto tmp = split(now -> r, a);
- change(tmp.first);
- change(tmp.second);
- now -> r = tmp.first;
- change(now);
- return {now, tmp.second};
- }
- auto tmp = split(now -> l, a);
- change(tmp.first);
- change(tmp.second);
- now -> l = tmp.second;
- change(now);
- return {tmp.first, now};
- }
- vertice* merge(vertice* t1, vertice* t2){
- if (t1 == NULL){
- return t2;
- }
- if (t2 == NULL){
- return t1;
- }
- if (t1 -> y > t2 -> y){
- t2 -> l = merge(t1, t2 -> l);
- change(t2);
- return t2;
- }
- t1 -> r = merge(t1 -> r, t2);
- change(t1);
- return t1;
- }
- vertice* add(int a, vertice* now){
- auto tmp = split(root, a);
- vertice* tmp2 = new vertice(a);
- return merge(merge(tmp.first, tmp2), tmp.second);
- }
- vertice* erase(int a){
- auto tl = split(root, a);
- auto tr = split(tl.second, a + 1);
- return merge(tl.first, tr.second);
- }
- void print(vertice* now, int sum){
- if (now == NULL){
- return;
- }
- print(now -> l, sum);
- cout << sum + c(now -> l) + 1 << " ";
- print(now -> r, sum + 1 + c(now -> l));
- }
- int main(){
- int n;
- cin >> n;
- int a;
- for (int i = 0; i < n; i++){
- cin >> a;
- root = add(a, root);
- }
- print(root, 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement