Splay裸题。。。
1. ADD x y D: 对区间[x, y]内的每一个树都加上D;2. REVERSE x y: 翻转区间
3. REVOLVE x y T: 旋转区间T次,相当于把区间的后半段(长度为T%(y-x+1))剪切黏贴到前面(调换顺序);
4. INSERT x P: 在x后插入p;
5. DELETE x: 删除x;
6. MIN x y: 求区间的最小值。
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAXN 200050
#define INF 0x3f3f3f3f
#define lson(k) (nn[k].ch[0])
#define rson(k) (nn[k].ch[1])
#define son(k, c) (nn[k].ch[c])
int a[MAXN]; //原数组
int n, m;
struct Node
{
int ch[2], fa;
int key, sz, flip, add, mink;
};
struct SplayTree
{
Node nn[MAXN];
int s[MAXN]; //内存池
int tot1, tot2;
int root;
void New(int &k, int fa, int key)
{
if(tot2) k = s[tot2--];
else k = ++tot1;
nn[k].key = nn[k].mink = key;
nn[k].fa = fa;
lson(k) = rson(k) = nn[k].flip = nn[k].add = 0;
nn[k].sz = 1;
}
void Pushup(int k)
{
nn[k].sz = 1;
nn[k].mink = nn[k].key;
if(lson(k)) nn[k].sz += nn[lson(k)].sz, nn[k].mink = min(nn[k].mink, nn[lson(k)].mink);
if(rson(k)) nn[k].sz += nn[rson(k)].sz, nn[k].mink = min(nn[k].mink, nn[rson(k)].mink);
}
void Pushdown(int k)
{
if(nn[k].flip)
{
nn[k].flip ^= 1;
swap(lson(k), rson(k));
if(lson(k)) nn[lson(k)].flip ^= 1;
if(rson(k)) nn[rson(k)].flip ^= 1;
}
if(nn[k].add)
{
for(int i = 0; i < 2; i++) if(son(k, i))
nn[son(k, i)].key += nn[k].add,
nn[son(k, i)].add += nn[k].add,
nn[son(k, i)].mink += nn[k].add;
nn[k].add = 0;
}
}
void Rotate(int k, int c)
{
Pushdown(k);
int a = son(k, c);
int y = nn[k].fa;
int z = nn[y].fa;
if(z) nn[z].ch[ rson(z) == y ] = k;
son(k, c) = y, son(y, c ^ 1) = a;
if(a) nn[a].fa = y;
nn[y].fa = k, nn[k].fa = z;
Pushup(y), Pushup(k);
}
void Splay(int k, int goal)
{
while(nn[k].fa != goal) Rotate(k, lson(nn[k].fa) == k);
if(goal == 0) root = k;
}
void Build(int &k, int fa, int l, int r)
{
if(l > r) return;
int m = (l + r) >> 1;
New(k, fa, a[m]) ;
Build(lson(k), k, l, m - 1);
Build(rson(k), k, m + 1, r);
Pushup(k);
}
void Init()
{
tot1 = tot2 = 0;
New(root, 0, -INF);
New(rson(root), root, INF);
Build(lson(rson(root)), rson(root), 1, n);
Pushup(rson(root));
Pushup(root);
}
int Select(int k, int f)
{
int t = root;
Pushdown(t);
int s = lson(t) ? nn[lson(t)].sz + 1 : 1;
while(s != k)
{
if(s < k) k -= s, t = rson(t);
else t = lson(t);
Pushdown(t);
s = lson(t) ? nn[lson(t)].sz + 1 : 1;
}
Splay(t, f);
return t;
}
void Add(int a, int b, int D)
{
int x = Select(a - 1, 0);
int y = Select(b + 1, x);
// Splay(x, 0); Splay(y, x);
int z = lson(y);
nn[z].key += D, nn[z].add += D, nn[z].mink += D;
Pushup(y);
Pushup(x);
}
void Reverse(int a,int b)
{
int x = Select(a - 1, 0);
int y = Select(b + 1, x);
// Splay(x, 0),Splay(y, x);
nn[lson(y)].flip ^= 1;
}
void Revolve(int a,int b, int T)
{
T %= b - a + 1;
if(T == 0) return;
int x = Select(b - T, 0);
int y = Select(b + 1, x);
// Splay(x, 0), Splay(y, x);
int tmp = lson(y);
lson(y) = 0;
Pushup(y), Pushup(x);
x = Select(a - 1, 0);
y = Select(a, x);
// Splay(x, 0), Splay(y, x);
lson(y) = tmp;
nn[tmp].fa = y;
Pushup(y), Pushup(x);
}
void Insert(int a, int P)
{
int x = Select(a, 0);
int y = Select(a + 1, x);
// Splay(x, 0), Splay(y, x);
New(lson(y), y, P);
Pushup(y);
Pushup(y);
}
void Erase(int &k)
{
if(!k) return ;
s[++tot2] = k;
Erase(lson(k));
Erase(rson(k));
k = 0;
}
void Delete(int a)
{
int x = Select(a - 1, 0);
int y = Select(a + 1, x);
// Splay(x, 0), Splay(y, x);
Erase(lson(y));
Pushup(y);
Pushup(x);
}
int Min(int a, int b)
{
int x = Select(a - 1, 0);
int y = Select(b + 1, x);
// Splay(x, 0), Splay(y, x);
return nn[lson(y)].mink;
}
}spt;
char op[20];
int main()
{
// freopen("3580.in", "r", stdin);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
spt.Init();
scanf("%d", &m);
int x, y, z;
while(m--)
{
scanf("%s", op);
if(op[0] == 'A')
{
scanf("%d%d%d", &x, &y, &z);
x++, y++ ;
spt.Add(x,y, z);
}
else if(op[0] == 'I')
{
scanf("%d%d",&x, &y);
x++;
spt.Insert(x, y);
}
else if(op[0] == 'D')
{
scanf("%d", &x);
x++;
spt.Delete(x);
}
else if(op[0] == 'M')
{
scanf("%d%d", &x, &y);
x++, y++;
printf("%d\n", spt.Min(x, y));
}
else if(op[3] == 'E')
{
scanf("%d%d", &x, &y);
x++, y++;
spt.Reverse(x, y);
}
else
{
scanf("%d%d%d",&x,&y, &z);
x++, y++;
spt.Revolve(x, y, z);
}
}
return 0;
}
更多推荐
POJ 3580 SuperMemo(Splay模板)
发布评论