SuperMemo
题目链接
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:
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}
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}
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}
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}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
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,就是代码量有点大
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <set>
#include <vector>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <climits>
#include <queue>
#include <stack>
using namespace std;
/* freopen("k.in", "r", stdin);
freopen("k.out", "w", stdout); */
//clock_t c1 = clock();
//std::cerr << "Time:" << clock() - c1 <<"ms" << std::endl;
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define de(a) cout << #a << " = " << a << endl
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef vector<int, int> VII;
#define inf 0x3f3f3f3f
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAXN = 1e6 + 7;
const ll MAXM = 5e6 + 7;
const ll MOD = 1e9 + 7;
const double eps = 1e-6;
const double pi = acos(-1.0);
int root = 0, N, tot = 0; //tot 总结点数量
int a[MAXN];
struct Node
{
int ch[2]; //子节点
int ff; //父节点
int cnt; //数量
int val; //值
int size; //儿子以及自己的总元素数量
int rev; //lazy标记
int lazy;
int minn;
void init(int x, int fa)
{
ff = ch[0] = ch[1] = 0;
size = 1;
val = x;
ff = fa;
cnt = 1;
lazy = 0;
minn = x;
rev = 0;
}
} t[MAXN];
void push_up(int u)
{
t[u].size = t[t[u].ch[0]].size + t[t[u].ch[1]].size + t[u].cnt;
t[u].minn = t[u].val;
if (t[u].ch[0])
t[u].minn = min(t[u].minn, t[t[u].ch[0]].minn);
if (t[u].ch[1])
t[u].minn = min(t[u].minn, t[t[u].ch[1]].minn);
}
void push_down(int now)
{
if (t[now].rev)
{
t[t[now].ch[0]].rev ^= 1;
t[t[now].ch[1]].rev ^= 1;
t[now].rev = 0;
swap(t[now].ch[0], t[now].ch[1]);
}
if (t[now].lazy)
{
if (t[now].ch[0])
{
t[t[now].ch[0]].lazy += t[now].lazy;
t[t[now].ch[0]].val += t[now].lazy;
t[t[now].ch[0]].minn += t[now].lazy;
}
if (t[now].ch[1])
{
t[t[now].ch[1]].lazy += t[now].lazy;
t[t[now].ch[1]].val += t[now].lazy;
t[t[now].ch[1]].minn += t[now].lazy;
}
t[now].lazy = 0;
}
}
void rotate(int x) //旋转
{
register int y = t[x].ff;
register int z = t[y].ff;
register int k = t[y].ch[1] == x; //x是y的左或右儿子
t[z].ch[t[z].ch[1] == y] = x;
t[x].ff = z;
t[y].ch[k] = t[x].ch[k ^ 1];
t[t[x].ch[k ^ 1]].ff = y;
t[x].ch[k ^ 1] = y;
t[y].ff = x;
push_up(y);
push_up(x);
}
void Splay(int x, int goal) //把x节点旋转到目标位置
{
while (t[x].ff != goal)
{
int y = t[x].ff;
int z = t[y].ff;
if (z != goal) //旋转
(t[y].ch[0] == x) ^ (t[z].ch[0] == y) ? rotate(x) : rotate(y);
rotate(x);
}
if (goal == 0)
root = x; //当前的根节点
}
void init()
{
root = tot = 0;
}
int buildtree(int l, int r, int fa)
{
if (l > r)
return 0;
int mid = (l + r) >> 1;
t[++tot].init(a[mid], fa);
int x = tot;
t[x].ch[0] = buildtree(l, mid - 1, x);
t[x].ch[1] = buildtree(mid + 1, r, x);
push_up(x);
return x;
}
int Kth(int k) //查找排名为x的序号
{
int u = root;
while (233)
{
push_down(u);
if (t[t[u].ch[0]].size >= k)
u = t[u].ch[0];
else if (t[t[u].ch[0]].size + 1 == k)
return u;
else
k -= t[t[u].ch[0]].size + 1, u = t[u].ch[1];
}
}
void ADD(int l, int r, int v) //区间+v
{
l = Kth(l);
r = Kth(r + 2);
Splay(l, 0);
Splay(r, l);
t[t[r].ch[0]].val += v;
t[t[r].ch[0]].minn += v;
t[t[r].ch[0]].lazy += v;
push_up(r);
push_up(l);
}
void reverse(int l, int r) //区间翻转
{
l = Kth(l);
r = Kth(r + 2);
Splay(l, 0);
Splay(r, l);
t[t[r].ch[0]].rev ^= 1;
}
void revolve(int l, int r, int k) //区间旋转k次
{
k = (k % (r - l + 1) + (r - l + 1)) % (r - l + 1);
if (!k)
return;
int x = Kth(r - k + 1);
int y = Kth(r + 2);
//把整段区间拿到前面
Splay(x, 0);
Splay(y, x);
int temp = t[y].ch[0];
t[y].ch[0] = 0;
push_up(y);
push_up(x);
x = Kth(l);
y = Kth(l + 1);
Splay(x, 0);
Splay(y, x);
t[y].ch[0] = temp;
t[temp].ff = y;
push_up(y);
push_up(x);
}
void Insert(int x, int v) //在第x数后面插入v
{
Splay(Kth(x + 1), 0);
Splay(Kth(x + 2), root);
t[++tot].init(v, t[root].ch[1]);
t[t[root].ch[1]].ch[0] = tot;
push_up(t[root].ch[1]);
push_up(root);
}
void del(int x)
{
Splay(Kth(x), 0);
Splay(Kth(x + 2), root);
t[t[root].ch[1]].ch[0] = 0;
push_up(t[root].ch[1]);
push_up(root);
}
int query(int l, int r)
{
int x = Kth(l);
int y = Kth(r + 2);
Splay(x, 0);
Splay(y, x);
return t[t[y].ch[0]].minn;
}
int main()
{
init();
int M;
scanf("%d", &N);
for (int i = 1; i <= N; i++)
scanf("%d", &a[i]);
a[0] = a[N + 1] = inf;
root = buildtree(0, N + 1, 0);
scanf("%d", &M);
while (M--)
{
char op[10];
scanf(" %s", op);
if (op[0] == 'A')
{
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
ADD(l, r, v);
}
else if (op[0] == 'R' && op[3] == 'O')
{
int l, r, t;
scanf("%d%d%d", &l, &r, &t);
revolve(l, r, t);
}
else if (op[0] == 'R')
{
int l, r;
scanf("%d%d", &l, &r);
reverse(l, r);
}
else if (op[0] == 'I')
{
int k, v;
scanf("%d%d", &k, &v);
Insert(k, v);
}
else if (op[0] == 'D')
{
int x;
scanf("%d", &x);
del(x);
}
else
{
int l, r;
scanf("%d%d", &l, &r);
printf("%d
", query(l, r));
}
}
return 0;
}