# 【題解】POJ 3580 SuperMemo

【題目敘述】https://vjudge.net/problem/POJ-3580
【解題想法】Treap

```#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define nullptr NULL

struct Treap{
int val;
int pri;
int sz;
int mn;
bool rev;
Treap* l;
Treap* r;
Treap(int x = 0){
val = x;
pri = (rand()<<16)|rand();
sz = 1;
mn = x;
rev = false;
l = nullptr;
r = nullptr;
}
};
int Size(Treap* t){
if (!t) return 0;
return t->sz;
}
int Min(Treap *t){
if (!t) return 1e9;
return t->mn;
}
void pull(Treap* t){
t->sz = Size(t->l) + Size(t->r) +1;
t->mn = min(min(Min(t->l), Min(t->r)), t->val);
}
void push(Treap *t){
if (t->rev){
swap(t->l, t->r);
if (t->l) t->l->rev ^= 1;
if (t->r) t->r->rev ^= 1;
t->rev = false;
}
if (t->l){
}
if (t->r){
}
}
}
Treap* Merge(Treap* a, Treap* b){
if (!a || !b){
if (!a) return b;
else return a;
}
if (a->pri > b->pri){
push(a);
a->r = Merge(a->r, b);
pull(a);
return a;
}
else{
push(b);
b->l = Merge(a, b->l);
pull(b);
return b;
}
}
void SplitBySize(Treap* t, int k, Treap*&a, Treap*&b){
if (!t){
a = nullptr;
b = nullptr;
return;
}
push(t);
if (Size(t->l) < k){
k -= Size(t->l)+1;
a = t;
SplitBySize(t->r, k, a->r, b);
pull(a);
}
else{
b = t;
SplitBySize(t->l, k, a, b->l);
pull(b);
}
}

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
string s;
Treap* root = nullptr;
cin >> n;
for (int i = 0, x; i < n; i++){
cin >> x;
root = Merge(root, new Treap(x));
}
cin >> q;
for (int i = 0; i < q; i++){
cin >> s;
if (s == "INSERT"){
int x, p;
cin >> x >> p;
Treap *a, *b;
SplitBySize(root, x, a, b);
a = Merge(a, new Treap(p));
root = Merge(a, b);
}
else if (s == "DELETE"){
int x;
cin >> x;
Treap *a, *b, *c;
SplitBySize(root, x-1, a, b);
SplitBySize(b, 1, c, b);
root = Merge(a, b);
}
else if (s == "MIN"){
int x, y;
cin >> x >> y;
Treap *a, *b, *c;
SplitBySize(root, x-1, a, b);
SplitBySize(b, y-x+1, b, c);
cout << b->mn << "\n";
b = Merge(b, c);
root = Merge(a, b);
}
else if (s == "REVOLVE"){
int x, y, t;
cin >> x >> y >> t;
t %= (y-x+1);
Treap *a, *b, *c, *d;
SplitBySize(root, x-1, a, b);
SplitBySize(b, y-x+1, b, d);
SplitBySize(b, y-x+1-t, b, c);
a = Merge(a, c);
a = Merge(a, b);
root = Merge(a, d);
}
else if (s == "REVERSE"){
int x, y;
cin >> x >> y;
Treap *a, *b, *c;
SplitBySize(root, x-1, a, b);
SplitBySize(b, y-x+1, b, c);
b->rev ^= 1;
b = Merge(b, c);
root = Merge(a, b);
}
int x, y, d;
cin >> x >> y >> d;
Treap *a, *b, *c;
SplitBySize(root, x-1, a, b);
SplitBySize(b, y-x+1, b, c);