POJ 3580 SuperMemo

TreapをVerifyするために解いた。

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cassert>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vl; typedef pair<ll,ll> pll; typedef vector<pll> vpll; typedef vector<string> vs;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

typedef int Val;
struct Node {
	Val val; int priority;
	Node *ch[2];
	//ここに欲しい情報(値のsum, 値のmin, etc.)
	//splitのためにデフォルトでsizeがある
	int size; Val mini;
	//遅延評価をするもの
	Val add; bool rev;
	//情報の初期値を設定する
	Node(Val v, int p)
		: val(v), priority(p)
		, size(1), add(0), rev(false), mini(v) { ch[0] = ch[1] = NULL; }
};
//NULL用に関数を作っておくと便利(Nodeのコンストラクタと同じく初期値に注意)
//addをvalやminiにも足している点に注意。こんなふうにできないと遅延評価はできない
Val val(Node *x) { assert(x); return x->val + x->add; }
int size(Node *x) { return !x ? 0 : x->size; }
Val mini(Node *x) { return !x ? INF : x->mini + x->add; }

Node *update(Node *x) {
	//ここで情報の更新を行う
	if(!x) return x;
	x->size = size(x->ch[0]) + 1 + size(x->ch[1]);
	x->mini = min(min(mini(x->ch[0]), mini(x->ch[1])), val(x));
	if(x->add) {
		x->val += x->add;
		if(x->ch[0]) x->ch[0]->add += x->add;
		if(x->ch[1]) x->ch[1]->add += x->add;
		x->add = 0;
	}
	if(x->rev) {
		swap(x->ch[0], x->ch[1]);
		if(x->ch[0]) x->ch[0]->rev ^= 1;
		if(x->ch[1]) x->ch[1]->rev ^= 1;
		x->rev = false;
	}
	return x;
}
Node *link(Node *x, Node *c, bool b) {
	x->ch[b] = c; return update(x);
}
Node *merge(Node *x, Node *y) {
	x = update(x); y = update(y);
	if(!x || !y) return x ? x : y;
	if(x->priority < y->priority) {
		return link(x, merge(x->ch[1], y), 1);
	}else {
		return link(y, merge(x, y->ch[0]), 0);
	}
}
//サイズによってsplitする。　([0,k) , [k,n))
typedef pair<Node*, Node*> NPair;
NPair split(Node *t, int k) {
	if(!update(t)) return mp((Node*)NULL, (Node*)NULL);
	if(size(t->ch[0]) < k) {
		NPair u = split(t->ch[1], k - size(t->ch[0]) - 1);
		return mp(link(t, u.first, 1), u.second);
	}else {
		NPair u = split(t->ch[0], k);
		return mp(u.first, link(t, u.second, 0));
	}
}
Node *singleton(Val val) { return update(new Node(val, rand())); }

int main() {
	int n;
	scanf("%d", &n);
	Node *t = NULL;
	rep(i, n) {
		Val a;
		scanf("%d", &a);
		t = merge(t, singleton(a));
	}
	int m;
	scanf("%d", &m);
	rep(i, m) {
		static char s[100];
		int x, y, a;
		scanf("%s", s);
		rep(i, 10) s[i] = toupper(s[i]);
		if(s[0] == 'A') {
			scanf("%d%d%d", &x, &y, &a); x--;
			NPair p = split(t, x); NPair q = split(p.second, y-x);
			q.first->add += a;
			t = merge(p.first, merge(q.first, q.second));
		}else if(s[0] == 'R' && s[3] == 'E') {
			scanf("%d%d", &x, &y); x--;
			NPair p = split(t, x); NPair q = split(p.second, y-x);
			q.first->rev ^= 1;
			t = merge(p.first, merge(q.first, q.second));
		}else if(s[0] == 'R' && s[3] == 'O') {
			scanf("%d%d%d", &x, &y, &a); x--; a %= (y - x);
			NPair p = split(t, x); NPair q = split(p.second, y-x); Node *m = q.first;
			NPair r = split(m, size(m) - a);
			t = merge(p.first, merge(merge(r.second, r.first), q.second));
		}else if(s[0] == 'I') {
			scanf("%d%d", &x, &a);
			NPair p = split(t, x);
			t = merge(p.first, merge(singleton(a), p.second));
		}else if(s[0] == 'D') {
			scanf("%d%d", &x); x--;
			NPair p = split(t, x); NPair q = split(p.second, 1);
			delete q.first;
			t = merge(p.first, q.second);
		}else if(s[0] == 'M') {
			scanf("%d%d", &x, &y); x--;
			NPair p = split(t, x); NPair q = split(p.second, y-x);
			printf("%d\n", mini(q.first));
			t = merge(p.first, merge(q.first, q.second));
		}
	}
	return 0;
}