POJ 3580 SuperMemo

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1, A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:

1. ADD x y D: Add D to each number in sub-sequence {Ax ... Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
2. REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
3. REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
4. INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
5. DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
6. MIN x y: query the participant what is the minimum number in sub-sequence {Ax ... Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5      

Sample Output

5

解决完splay终极boss以后这种题写起来就十分轻松了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 1e5 + 10;
int n, m, root, a[maxn], l, r, c;
char s[20];

struct Splays
{
	const static int maxn = 2e5 + 10;			//节点个数
	const static int INF = 0x7FFFFFFF;			//int最大值
	int ch[maxn][2], F[maxn], sz;				//左右儿子，父亲节点和节点总个数
	int A[maxn], S[maxn], C[maxn], R[maxn], I[maxn];
	int Node(int f, int a) { S[sz] = 1; C[sz] = A[sz] = a; R[sz] = I[sz] = ch[sz][0] = ch[sz][1] = 0; F[sz] = f; return sz++; }//申请一个新节点
	void clear(){ sz = 1; S[0] = ch[0][0] = ch[0][1] = F[0] = 0; C[0] = INF; }//清空操作
	void Pushdown(int x)
	{
		if (R[x])
		{
			R[ch[x][0]] ^= 1;	R[ch[x][1]] ^= 1;
			swap(ch[x][0], ch[x][1]);	R[x] = 0;
		}
		if (I[x])
		{
			if (ch[x][0]) A[ch[x][0]] += I[x], C[ch[x][0]] += I[x];
			if (ch[x][1]) A[ch[x][1]] += I[x], C[ch[x][1]] += I[x];
			I[ch[x][0]] += I[x]; I[ch[x][1]] += I[x];	  I[x] = 0;
		}
	}
	void Count(int x)
	{
		C[x] = min(A[x], min(C[ch[x][0]], C[ch[x][1]])); 
		S[x] = S[ch[x][0]] + S[ch[x][1]] + 1;
	}
	void rotate(int x, int k)
	{
		int y = F[x]; ch[y][!k] = ch[x][k]; F[ch[x][k]] = y;
		if (F[y]) ch[F[y]][y == ch[F[y]][1]] = x;
		F[x] = F[y];    F[y] = x;	ch[x][k] = y;
		C[x] = C[y];	S[x] = S[y];    Count(y);
	}
	void Splay(int x, int r)
	{
		for (int fa = F[r]; F[x] != fa;)
		{
			if (F[F[x]] == fa) { rotate(x, x == ch[F[x]][0]); return; }
			int y = x == ch[F[x]][0], z = F[x] == ch[F[F[x]]][0];
			y^z ? (rotate(x, y), rotate(x, z)) : (rotate(F[x], z), rotate(x, y));
		}
	}
	void build(int fa, int &x, int l, int r)
	{
		if (l > r) return;
		int mid = l + r >> 1;
		x = Node(fa, a[mid]);
		build(x, ch[x][0], l, mid - 1);
		build(x, ch[x][1], mid + 1, r);
		Count(x);
	}
	void find(int &x, int k)
	{
		for (int i = x; i;)
		{
			Pushdown(i);
			if (S[ch[i][0]] > k) { i = ch[i][0]; continue; }
			if (S[ch[i][0]] == k){ Splay(i, x); x = i; return; }
			k -= S[ch[i][0]] + 1;	i = ch[i][1];
		}
	}
	void Add(int&x)
	{
		scanf("%d%d%d", &l, &r, &c);
		find(x, l - 1);	find(ch[x][1], r - l + 1);
		int g = ch[ch[x][1]][0];
		I[g] += c;	A[g] += c;	C[g] += c;
		Count(ch[x][1]);	Count(x);
	}
	void Reverse(int &x)
	{
		scanf("%d%d", &l, &r);
		find(x, l - 1);	find(ch[x][1], r - l + 1);
		R[ch[ch[x][1]][0]] ^= 1;
	}
	void Revolve(int &x)
	{
		scanf("%d%d%d", &l, &r, &c);
		find(x, l - 1);	find(ch[x][1], r - l + 1);
		int g = ch[ch[x][1]][0]; c %= (r - l + 1);
		if (!c) return;
		int s = r - l + 1 - c;	find(g, s);
		int t = ch[g][0];	ch[g][0] = 0;	Count(g);
		find(g, S[g] - 1);	ch[g][1] = t;	F[t] = g;	Count(g);
	}
	void Insert(int &x)
	{
		scanf("%d%d", &l, &r);
		find(x, l);	find(ch[x][1], 0);
		ch[ch[x][1]][0] = Node(ch[x][1], r);
		Count(ch[x][1]);	Count(x);
	}
	void Delete(int &x)
	{
		scanf("%d%d", &l);
		find(x, l - 1);	find(ch[x][1], 1);
		ch[ch[x][1]][0] = 0;
		Count(ch[x][1]);	Count(x);
	}
	void Min(int &x)
	{
		scanf("%d%d", &l, &r);
		find(x, l - 1);	find(ch[x][1], r - l + 1);
		printf("%d\n", C[ch[ch[x][1]][0]]);
	}
}solve;


int main()
{
	while (scanf("%d", &n) != EOF)
	{
		a[0] = a[n + 1] = root = 0;	solve.clear();
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		solve.build(0, root, 0, n + 1);
		scanf("%d", &m);
		while (m--)
		{
			scanf("%s", s);
			if (!strcmp(s, "ADD")) solve.Add(root);
			if (!strcmp(s, "REVERSE")) solve.Reverse(root);
			if (!strcmp(s, "REVOLVE")) solve.Revolve(root);
			if (!strcmp(s, "INSERT")) solve.Insert(root);
			if (!strcmp(s, "DELETE")) solve.Delete(root);
			if (!strcmp(s, "MIN")) solve.Min(root);
		}
	}
	return 0;
}