题目链接：http://hihocoder.com/problemset/problem/1329
这题本来是学Splay的题，但是我为了练习Treap的Split和Merge操作，就借来用一用。
就是砍树然后再合并。
存个代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <numeric>
#include <iterator>
#include <iostream>
#include <cstdlib>
#include <functional>
#include <queue>
#include <stack>
#include <list>
#include <ctime>
using namespace std; const int inf = ~0U >> ; typedef long long LL; struct TreapNode {
int key, val, siz;
TreapNode* ch[];
TreapNode() :val(), siz(){ key = rand(); ch[] = ch[] = NULL; }
void rz(){
siz = ;
if (ch[]) siz += ch[]->siz;
if (ch[]) siz += ch[]->siz;
}
~TreapNode(){
if (ch[]) delete ch[];
if (ch[]) delete ch[];
}
}; typedef pair<TreapNode*, TreapNode*> DTreap; void rot(TreapNode*& rt, bool d){
TreapNode* c = rt->ch[d];
rt->ch[d] = c->ch[!d];
c->ch[!d] = rt;
rt->rz(); c->rz();
rt = c;
} void Insert(TreapNode*& rt, int val, int key = ) {
if (!rt){
rt = new TreapNode();
rt->val = val;
if (key) rt->key = key;
return;
}
//if (val == rt->val) return;
bool d = val > rt->val;
Insert(rt->ch[d], val, key);
if (rt->ch[d]->key < rt->key) rot(rt, d);
else rt->rz();
} void Delete(TreapNode*& rt, int val) {
if (rt == NULL) return;
if (rt->val == val) {
if (rt->ch[] == NULL && rt->ch[] == NULL) {
delete rt;
rt = NULL;
return;
}
else if (rt->ch[] == NULL) {
rot(rt, );
Delete(rt->ch[], val);
}
else if (rt->ch[] == NULL) {
rot(rt, );
Delete(rt->ch[], val);
}
else {
bool d = rt->ch[]->key > rt->ch[]->key;
rot(rt, d);
Delete(rt->ch[!d], val);
}
}
else {
bool d = val > rt->val;
Delete(rt->ch[d], val);
}
rt->rz();
} int Kth(TreapNode* rt, int k) {
if (!rt) return -inf;
if (rt->siz < k) return -inf;
int r = ;
if (!rt->ch[]) r = ;
else r = rt->ch[]->siz;
if (r == k - ) return rt->val;
if (k - < r) return Kth(rt->ch[], k);
return Kth(rt->ch[], k - r - );
} DTreap Split(TreapNode* rt, int val) {
DTreap ret;
Insert(rt, val, -inf);
ret.first = rt->ch[];
ret.second = rt->ch[];
rt->ch[] = rt->ch[] = NULL;
delete rt;
return ret;
} void Merge(DTreap dt, TreapNode*& rt) {
rt = NULL;
TreapNode* tch = dt.first?dt.first:dt.second;
if(tch) {
TreapNode* nd = new TreapNode();
nd->key = -inf;
nd->val = tch->val;
nd->ch[] = dt.first;
nd->ch[] = dt.second;
rt = nd;
Delete(rt, nd->val);
}
} int ans; void Query(TreapNode* rt, int x) {
if (rt == NULL) return;
if (rt->val == x) {
ans = x;
return;
}
if (rt->val > x) {
Query(rt->ch[], x);
}
else {
ans = max(ans, rt->val);
Query(rt->ch[], x);
}
} char cmd[];
int a, b, n; int main() {
srand(time(NULL));
scanf("%d", &n);
TreapNode* root = NULL;
for (int i = ; i < n; i++) {
scanf("%s", cmd);
if (cmd[] == 'I') {
scanf("%d", &a);
Insert(root, a);
}
else if (cmd[] == 'Q') {
ans = -inf;
scanf("%d", &a);
Query(root, a);
printf("%d\n", ans);
}
else {
scanf("%d%d", &a, &b);
DTreap dt = Split(root, a);
TreapNode* lch = dt.first;
TreapNode* rch = dt.second;
dt = Split(rch, b + );
if (dt.first) delete dt.first;
dt.first = lch;
Merge(dt, root);
}
}
if (root) delete root;
return ;
}