Treap 模板 (一般)

目前是沒有LAZY TAG的

http://zerojudge.tw/ShowProblem?problemid=d539

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
using namespace std;

const int INF = 1000000000;

struct Treap {
Treap *lc;
Treap *rc;
int val,pri,key;
int add;
int mx;
Treap(int _val,int _key) {
val=_val;
key=_key;
mx=val;
pri=rand();
add=0;
lc = rc = NULL;
}
};

int mx(Treap* t) {
return t? t->mx + t->add : -INF;
}

void pull(Treap* t) {
t->mx= max(t->val, max(mx(t->lc), mx(t->rc)) );
}

void push(Treap* t) {
t->val += t->add;
if (t->lc) t->lc->add += t->add;
if (t->rc) t->rc->add += t->add;
t->add = 0;
}

Treap* merge(Treap *a,Treap *b) {
// puts("in0");
if (!a || !b) return a?a:b;
if (a->pri > b->pri) {
push(a);
// puts("in1");
// cout<<"a->val = "<<a->val<<endl;
a->rc=merge(a->rc,b);
pull(a);
return a;
}
else {
push(b);
// puts("in2");
// cout<<"b->val = "<<b->val<<endl;
b->lc=merge(a,b->lc);
pull(b);
return b;
}
}

void split(Treap* t, int x,Treap* &a, Treap* &b) {
if (!t) a = b = NULL;
else if (t->key<=x) {
a=t;
push(a);
split(t->rc,x,a->rc,b);
pull(a);
}
else {
b=t;
push(b);
split(t->lc,x,a,b->lc);
pull(b);
}
}

int rmq(Treap *t,int l,int r) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
// puts("in");
int ret=mx(t);
t=merge(merge(tl,t),tr);
return ret;
}

void add(Treap* t,int l,int r,int v) {
Treap *tl, *tr;
split(t,l-1,tl,t);
split(t,r,t,tr);
t->add += v;
t=merge(merge(tl,t),tr);
}

int main () {
srand(time(NULL));
int n;
while (scanf("%d",&n) != EOF) {
Treap* root;
root=NULL;
for (int x=1;n>=x;x++) {
int i;
scanf("%d",&i);
root = merge(root,new Treap(i,x));
}
int q;
scanf("%d",&q);
while (q--) {
int i,j;
scanf("%d %d",&i,&j);
if (i>j) swap(i,j);
printf("%d\n",rmq(root,i,j));
}
}
}