1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253 |
- #include <bits/stdc++.h>
- using namespace std;
- #include "Treap.cpp"
- int main() {
- int values[] = {6,5,4,1,2,3}, n = sizeof(values)/sizeof(int);
- Node *r = NULL;
- for(int i = 0; i < n; i++)
- merge(r, r, new Node(values[i]));
- assert(query(r, 1, 6) == 21);
- assert(query(r, 1, 3) == 15);
- assert(query(r, 3, 4) == 5);
- reverse(r, 1, 3); // 4 5 6 1 2 3
- assert(query(r, 1, 3) == 15);
- assert(query(r, 3, 4) == 7);
- reverse(r, 1, 6); // 3 2 1 6 5 4
- assert(query(r, 1, 6) == 21);
- assert(query(r, 5, 6) == 9);
- insert(r, 2, 8); // 3 8 2 1 6 5 4
- assert(query(r, 2, 2) == 8);
- assert(query(r, 1, 3) == 13);
- insert(r, 3, 2); // 3 8 2 2 1 6 5 4
- assert(query(r, 1, 4) == 15);
- del(r, 3); // 3 8 2 1 6 5 4
- assert(query(r, 2, 2) == 8);
- assert(query(r, 1, 3) == 13);
- del(r, 1); // 8 2 1 6 5 4
- assert(query(r, 2, 5) == 14);
- del(r, 2);
- del(r, 3);
- del(r, 2);
- del(r, 2);
- del(r, 1);
- del(r, 1); //
- assert(query(r, 1, 5) == 0);
- r = NULL;
- insert(r, 1, 10); // 10
- insert(r, 1, 2); // 2 10
- assert(query(r, 1, 1) == 2);
- assert(query(r, 1, 2) == 12);
- del(r, 2);
- del(r, 1); //
- r = NULL;
- insert(r, 1, 3); // 3
- assert(query(r, 1, 1) == 3);
- insert(r, 2, 2); // 3 2
- assert(query(r, 1, 2) == 5);
- assert(query(r, 2, 2) == 2);
- return 0;
- }
|