123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111 |
- // Cartesian tree (treap)
- // Compute sum (here) of a range, and can reverse a range
- // COMPLEXITY on average : construction O(nlog n)?, operations O(log n), lazy reversal
- // all ranges are 1-based
- struct Node {
- int y, sz;
- long long v, sm;
- bool rev;
- struct Node *l, *r;
- Node(long long v) : v(v) {
- y = rand();
- sm = v;
- rev = false;
- sz = 1;
- l = r = NULL;
- }
- };
- typedef struct Node Node;
- int size(Node *n) {
- return n != NULL ? n->sz : 0;
- }
- long long sum(Node *n) {
- return n != NULL ? n->sm : 0;
- }
- void update(Node *n) {
- if(n != NULL) {
- n->sm = n->v + sum(n->l) + sum(n->r);
- n->sz = 1 + size(n->l) + size(n->r);
- }
- }
- void push(Node *n) { // push reverse flag
- if(n != NULL && n->rev) {
- swap(n->l, n->r);
- n->rev = false;
- if(n->l != NULL)
- n->l->rev ^= true;
- if(n->r != NULL)
- n->r->rev ^= true;
- }
- }
- void merge(Node* &n, Node *l, Node *r) {
- push(l); push(r);
- if(l == NULL) {
- n = r; return;
- }
- if(r == NULL) {
- n = l; return;
- }
- if(l->y > r->y) {
- merge(l->r, l->r, r);
- n = l;
- }
- else {
- merge(r->l, l, r->l);
- n = r;
- }
- update(n);
- }
- // x stays in r
- void split(Node *n, Node* &l, Node* &r, int x, int add = 0) {
- push(n);
- if(n == NULL) {
- l = r = NULL; return;
- }
- int key = size(n->l) + 1 + add;
- if(x <= key) {
- split(n->l, l, n->l, x, add);
- r = n;
- }
- else {
- split(n->r, n->r, r, x, key);
- l = n;
- }
- update(n);
- }
- // reverse [l, r] (1-based)
- void reverse(Node* &n, int l, int r) {
- Node *a, *b;
- split(n, n, a, l, 0);
- split(a, a, b, r - l + 2, 0);
- a->rev ^= true;
- merge(n, n, a);
- merge(n, n, b);
- }
- // query sum of [l, r] (1-based)
- long long query(Node* &n, int l, int r) {
- long long ans;
- Node *a, *b;
- split(n, n, a, l, 0);
- split(a, a, b, r - l + 2, 0);
- ans = sum(a);
- merge(n, n, a);
- merge(n, n, b);
- return ans;
- }
- // insert value v at position p (if p <= size, at the end if p > size)
- void insert(Node* &n, int p, long long v) {
- Node *a;
- split(n, n, a, p);
- merge(n, n, new Node(v));
- merge(n, n, a);
- }
- // delete element at position p (if any)
- void del(Node* &n, int p) {
- Node *a, *b;
- split(n, n, a, p);
- split(a, a, b, 2);
- merge(n, n, b);
- if(a)
- delete a;
- }
|