链接
POJ 3580 SuperMemo
题意
Splay Tree模板题
思路
第一次写伸展树, 主要参考了 运用伸展树解决数列维护问题.pdf。 看了别人的代码,自己重新写了一下。解释见注释
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
#define MAXN 200005
#define INF 0x3f3f3f3f
#define MEM(some) memset(some, 0, sizeof(some))
using namespace std;
int a[MAXN];
struct Splay{
int father[MAXN], num[MAXN], son[MAXN][2], value[MAXN], add[MAXN], minv[MAXN], reverse[MAXN];
int root, n;
void init(int m){
//初始化
MEM(father), MEM(num), MEM(son), MEM(value), MEM(value), MEM(minv), MEM(reverse);
n = 0;
root = 1;
build(root, 1, m, 0);
}
void create(int &x, int fa, int val){
//新增节点到树中
x = ++n;
father[x] = fa;
value[x] = minv[x] = val;
num[x] = 1;
}
void build(int &x, int left, int right, int fa){
//原序列 = 伸展树的中序遍历
if (left > right) return;
int mid = (left + right) >> 1;
create(x, fa, a[mid]);
build(son[x][0], left, mid - 1, x);
build(son[x][1], mid + 1, right, x);
//这里是维护num[]
maintain(x);
}
void maintain(int x){
num[x] = num[son[x][0]] + num[son[x][1]] + 1;
minv[x] = value[x];
if (son[x][0]){
minv[x] = min(minv[x], minv[son[x][0]] + add[x]);
}
if (son[x][1]){
minv[x] = min(minv[x], minv[son[x][1]] + add[x]);
}
}
void pushdown(int x){
//标记下传
if (reverse[x]){
//交换左右儿子,等价于翻转
swap(son[x][0], son[x][1]);
if (son[x][0]){
reverse[son[x][0]] ^= 1;
}
if (son[x][1]){
reverse[son[x][1]] ^= 1;
}
reverse[x] = 0;
}
if (add[x]){
if (son[x][0]){
add[son[x][0]] += add[x];
minv[son[x][0]] += add[x];
value[son[x][0]] += add[x];
}
if (son[x][1]){
add[son[x][1]] += add[x];
minv[son[x][1]] += add[x];
value[son[x][1]] += add[x];
}
add[x] = 0;
}
}
int get_pos(int x, int k){
//获取序列中数字在伸展树中的编号
pushdown(x);
int temp = 0;
if (son[x][0]){
temp = num[son[x][0]];
}
if (temp == k - 1){
//恰好是当前节点
return x;
}
else if (temp >= k){
//在左子树中
return get_pos(son[x][0], k);
}
else{
//在右子树中
return get_pos(son[x][1], k - (temp + 1));
}
}
void rotate(int x){
//旋转 右旋或左旋
int y = father[x];
int kind = (son[y][1] == x);
pushdown(y);
pushdown(x);
son[y][kind] = son[x][!kind];
if (son[y][kind]){
father[son[y][kind]] = y;
}
father[x] = father[y];
father[y] = x;
son[x][!kind] = y;
if (y == root){
root = x;
}
else{
son[father[x]][son[father[x]][1] == y] = x;
}
maintain(y);
maintain(x);
}
void splay(int x, int fa){
//将x旋转到fa的儿子
while (father[x] != fa){
int y = father[x];
int z = father[y];
if (father[y] == fa){
//单旋转
rotate(x);
}
else if ((son[y][1] == x) ^ (son[z][1] == y)){
//之字形旋转
rotate(x);
rotate(x);
}
else {
//一字形旋转
rotate(y);
rotate(x);
}
}
}
void Add(int a, int b, int c){
//区间a-b都加上c
int x = get_pos(root, a);
int y = get_pos(root, b);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
int z = son[y][0];
add[z] += c;
value[z] += c;
minv[z] += c;
maintain(y);
maintain(x);
}
void Reverse(int a, int b){
//翻转区间a-b
int x = get_pos(root, a);
int y = get_pos(root, b);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
int z = son[y][0];
reverse[z] ^= 1;
maintain(y);
maintain(x);
}
void Revolve(int a, int b, int c){
//区间a-b滚动c个长度, 将序列位置为b-1的换到a处
//实际上把a-b区间的插入到c位置的后面
int x = get_pos(root, a);
int y = get_pos(root, b);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
int z = son[y][0];
son[y][0] = 0;
maintain(y);
maintain(x);
//插入
int u = get_pos(root, c);
int v = get_pos(root, c + 1);
splay(u, 0);
splay(v, root);
pushdown(u);
pushdown(v);
son[v][0] = z;
father[z] = v;
maintain(v);
maintain(u);
}
void Insert(int a, int b){
//位置a添加b
int x = get_pos(root, a);
int y = get_pos(root, a + 1);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
create(son[y][0], y, b);
maintain(y);
maintain(x);
}
void Delete(int a, int b){
//删除区间a-b
int x = get_pos(root, a);
int y = get_pos(root, b);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
int z = son[y][0];
son[y][0] = 0;
father[z] = 0;
maintain(y);
maintain(x);
}
int QueryMin(int a, int b){
//区间a-b的最小值
int x = get_pos(root, a);
int y = get_pos(root, b);
splay(x, 0);
splay(y, root);
pushdown(x);
pushdown(y);
int z = son[y][0];
maintain(y);
maintain(x);
return minv[z];
}
};
Splay res;
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
int n, m;
while (~scanf("%d", &n)){
for (int i = 1; i <= n; ++i){
scanf("%d", &a[i + 1]);
}
a[1] = a[n + 2] = INF;
res.init(n + 2);
scanf("%d", &m);
int x, y, z;
for (int i = 1; i <= m; ++i){
char s[10];
scanf("%s", s);
if (s[0] == 'A'){
scanf("%d%d%d", &x, &y, &z);
res.Add(x, y + 2, z);
}
else if (s[0] == 'R' && s[3] == 'E'){
scanf("%d%d", &x, &y);
res.Reverse(x, y + 2);
}
else if (s[0] == 'R' && s[3] == 'O'){
scanf("%d%d%d", &x, &y, &z);
//把 z 规范到 0 ~ (y - x +1)
z = (z % (y - x + 1) + (y - x + 1)) % (y - x + 1);
if (z){
res.Revolve(y + 2 - z - 1, y + 2, x);
}
}
else if (s[0] == 'I'){
scanf("%d%d", &x, &y);
res.Insert(x + 1, y);
}
else if (s[0] == 'D'){
scanf("%d", &x);
res.Delete(x, x + 2);
}
else{
scanf("%d%d", &x, &y);
printf("%d\n", res.QueryMin(x, y + 2));
}
}
}
}
查看原文:http://www.macinchang/2016/02/26/559/
更多推荐
POJ 3580 SuperMemo SplayTree
发布评论