SuperMemo
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 17279 | Accepted: 5449 | |
Case Time Limit: 2000MS |
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:
- 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
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu
【思路】
要求实现的数据结构,必须具备如下功能:1、区间加数,2、求区间最小值,3、区间翻转,4、区间流动,5、在特定位置插入一个数,6、在特定位置删除一个数。
分析一下,1和2是线段树的经典功能,3、4、5、6线段树就真的无能为力了,毕竟元素在树中位置已经固定,导致移动、增删乏力。所以此题需要有一种更加强大的结构,它得满足低时间复杂度的移动的要求。于是Splay树闪亮登场——这真的是神一般的数据结构啊。
对于Splay的单旋、双旋和splay操作就不再这里多说了,读者可先搜索了解其原理再来看本文。出于思维习惯,我的Splay树实现是数组版本的,所以内存池也就只需记录回收的下标就可以了,这也省去了许多指针带来的麻烦。维护的数组有:父节点fa[MAXN],子节点son[MAXN][2],子树大小sz[MAXN],键值val[MAXN],子树最小值mn[MAXN],加法标记add_mark[MAXN],翻转标记reverse_mark[MAXN]。
首先,所有以上六个操作都得从区间提取这一步说起。对于一个区间[1, n],我们右挪一下,相当于加个头,再加个尾,变成[1, n + 2],原先1到n的元素,如今映射至2到n+1上。这样对任意区间[a, b],将a - 1节点splay到root,将b + 1节点splay到root之下,这样以根的右孩子的左孩子作为根的整棵子树就是提取出来的区间[a, b]了。此后在区间上的操作便和线段树思想相近,但是妙的地方在于它还多了移动、增删的功能。下面逐个分析:
对于ADD、REVERSE操作,就是在子树根打上标记,同时做实质性更新,最后splay区间树根到根节点。
对于MIN操作,就是查询区间树根mn值,最后splay区间树根到根节点。
对于REVOLVE操作,就是将一段区间挪到另一段的另一侧,最后splay区间树根到根节点。
对于INSERT、DELETE操作,就是提取完合适的区间后,在根的右孩子加上一个左孩子或者删除左孩子,最后splay区间树根到根节点,如果是DELETE就splay被删除元素的父节点。
其实Splay里多是对子树进行操作,移动子树树根的方式多种多样,所以不必拘泥于一家之言。如果按照我的这一做法,则需要特别注意:
1、对于将要splay的节点,必须是一路从根找下去找到的节点,这样才能完全push_down沿途标记。
2、在开始splay之前还应该push_down当前节点,让标记下移且对子节点有实质性改变,一定要有实质性改变,mn和val都得修改,否则很可能在未来的操作中就再也没机会修改到了。同理ADD和REVERSE也都得对子树树根进行实质性修改。
3、然后splay过程中每一步rotate时,都要push_down将要交接的子节点一下,然后再update被挪下去的父节点。
4、不必每一步rotate都update自己,只需最后再update自己就好,因为中途当前节点的信息会被立马修改,这一步是多余的,我们只需要保证splay完成后的信息正确便可。
5、虽然题目没说,但可能会由于过多删除和插入,导致需要的内存开销过大,这里采取了数组版本的内存池,删除节点后回收内存以备后用。
相当重口味的一道题目,也算是我转战Linux和Vim的第一个有意义的里程碑吧!两个星期都在思考Splay,有一天睡得早说梦话竟然提到了它,舍友表示三脸懵逼。经过稍有间断的思考,两天前晚上觉得大致时机成熟了,开始写了个头,结果竟然调试了整整一天,当然途中看的、思考的东西也不少,做了许多其他人没做的常数级别的优化,一整棵树都是用模拟指针实现的。
【代码】
//************************************************************************
// File Name: main.cpp
// Author: Shili_Xu
// E-Mail: shili_xu@qq
// Created Time: 2018年01月04日 星期四 23时11分52秒
//************************************************************************
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXN = 2e5 + 5, INF = 0x3fffffff;
int n, m, root, mem;
int val[MAXN], fa[MAXN], sz[MAXN], mn[MAXN], reverse_mark[MAXN], add_mark[MAXN];
int son[MAXN][2];
stack<int> st;
void push_down(int x)
{
if (add_mark[x]) {
if (son[x][0]) add_mark[son[x][0]] += add_mark[x], val[son[x][0]] += add_mark[x], mn[son[x][0]] += add_mark[x];
if (son[x][1]) add_mark[son[x][1]] += add_mark[x], val[son[x][1]] += add_mark[x], mn[son[x][1]] += add_mark[x];
add_mark[x] = 0;
}
if (reverse_mark[x]) {
if (son[x][0]) reverse_mark[son[x][0]] ^= 1, swap(son[son[x][0]][0], son[son[x][0]][1]);
if (son[x][1]) reverse_mark[son[x][1]] ^= 1, swap(son[son[x][1]][0], son[son[x][1]][1]);
reverse_mark[x] = 0;
}
}
void update(int x)
{
sz[x] = 1;
mn[x] = val[x];
if (son[x][0]) sz[x] += sz[son[x][0]], mn[x] = min(mn[x], mn[son[x][0]]);
if (son[x][1]) sz[x] += sz[son[x][1]], mn[x] = min(mn[x], mn[son[x][1]]);
}
void rotate(int x, int dir)
{
int y = fa[x], z = fa[y];
son[y][!dir] = son[x][dir]; if (son[x][dir]) fa[son[x][dir]] = y;
if (z) son[z][son[z][1] == y] = x; fa[x] = z;
son[x][dir] = y; fa[y] = x;
update(y);
if (root == y) root = x;
}
void splay(int x, int f)
{
push_down(x);
while (fa[x] != f) {
if (fa[fa[x]] == f)
if (son[fa[x]][0] == x) rotate(x, 1); else rotate(x, 0);
else {
int y = fa[x], z = fa[y];
if (son[z][0] == y)
if (son[y][0] == x) rotate(y, 1), rotate(x, 1); else rotate(x, 0), rotate(x, 1);
else
if (son[y][1] == x) rotate(y, 0), rotate(x, 0); else rotate(x, 1), rotate(x, 0);
}
}
update(x);
}
void select(int k, int f)
{
k++;
int now = root, tmp;
while (true) {
push_down(now);
if (son[now][0]) tmp = sz[son[now][0]]; else tmp = 0;
if (k == tmp + 1) break;
if (k <= tmp)
now = son[now][0];
else {
now = son[now][1];
k -= (tmp + 1);
}
}
splay(now, f);
}
void select_segment(int l, int r)
{
select(l - 1, 0);
select(r + 1, root);
}
void insert(int x, int num)
{
select_segment(x, x - 1);
int now;
if (st.empty())
now = ++mem;
else {
now = st.top();
st.pop();
}
val[now] = num;
sz[now] = 1;
mn[now] = num;
fa[now] = son[root][1];
son[now][0] = son[now][1] = 0;
add_mark[now] = reverse_mark[now] = 0;
splay(now, 0);
}
void add(int l, int r, int num)
{
select_segment(l, r);
int now = son[son[root][1]][0];
add_mark[now] += num;
val[now] += num;
mn[now] += num;
splay(now, 0);
}
void reverse(int l, int r)
{
select_segment(l, r);
int now = son[son[root][1]][0];
reverse_mark[now] ^= 1;
swap(son[now][0], son[now][1]);
splay(now, 0);
}
void revolve(int l, int r, int t)
{
t = t % (r - l + 1);
if (t < 0) t = r - l + 1 + t;
if (!t) return;
select_segment(l, r);
select(r - t, son[root][1]);
int now = son[son[root][1]][0], right = son[now][1];
son[now][1] = 0;
select(l, son[root][1]);
now = son[son[root][1]][0];
son[now][0] = right; fa[right] = now;
splay(now, 0);
}
void del(int x)
{
select_segment(x, x);
int now = son[root][1];
st.push(son[now][0]);
son[now][0] = 0;
splay(now, 0);
}
long long get_min(int l, int r)
{
select_segment(l, r);
int now = son[son[root][1]][0];
return mn[now];
}
void init()
{
mem = 0;
root = ++mem; fa[root] = 0;
son[root][1] = ++mem; fa[son[root][1]] = root;
son[root][0] = son[son[root][1]][0] = son[son[root][1]][1] = 0;
add_mark[root] = add_mark[son[root][1]] = 0;
reverse_mark[root] = reverse_mark[son[root][1]] = 0;
val[root] = val[son[root][1]] = INF;
update(son[root][1]); update(root);
}
int main()
{
init();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int num;
scanf("%d", &num);
insert(i, num);
}
scanf("%d", &m);
char mes[8];
int a, b, c;
while (m--) {
scanf("%s", mes);
if (mes[0] == 'A') {
scanf("%d %d %d", &a, &b, &c);
add(a, b, c);
}
if (mes[0] == 'R' && mes[3] == 'E') {
scanf("%d %d", &a, &b);
reverse(a, b);
}
if (mes[0] == 'R' && mes[3] == 'O') {
scanf("%d %d %d", &a, &b, &c);
revolve(a, b, c);
}
if (mes[0] == 'I') {
scanf("%d %d", &a, &b);
insert(a + 1, b);
}
if (mes[0] == 'D') {
scanf("%d", &a);
del(a);
}
if (mes[0] == 'M') {
scanf("%d %d", &a, &b);
printf("%lld\n", get_min(a, b));
}
}
return 0;
}
更多推荐
POJ 3580 SuperMemo(Splay树+内存池)
发布评论