如果不懂splay,请进入百度文库,如果看懂了就忽略此文
题源:poj3580
splay,伸展树,是一颗功能好的平衡树,它通过把操作过的询问旋到根,来节省时间,使得总时间为log(迷之常数....)所以我们要维护一个序列,就不能像treap那样通过权值大小忽略位置地直接比较,以下是要注意的。
!!!:工作原理:提取a-1,b+1相当于提取整个区间。
1.我们最开始通过二分把信息塞进splay(按照位置,不是大小)注意
2.初始化时把根0的信息清0,塞进两个大哨兵,在下面那个哨兵的左子树建好(使得序列左边有一个,右边又一个,为了鲁棒性和方便性,这时很好的)
3.旋转操作看着复杂,画个图,其实改变的只有两个东西(或许一个? !-_-!)
4.我们通过名次树的那个size来找到序列位置,旋到跟。
5.注意使用lazy—tag,我们为了在id(名次)draw(提取)中使用了pushdown操作,那个pushroad也是从root一直pushdown(写成stack放爆),注意多次使用maintain(尤其是修改了啊,建树时啊),不要以为lazy-tag比线段树慢,其实也是很快的。
6.本处的rub数组他的本意一样使用了回收内存,他的含义是找到没用的下标,回收。
7.那个reserve是不是很难?其实不然,交换子树打标记,配合pushdown完成工作,
当然啊,你用草稿纸模拟一片,他是对的(二分思想)。
8.revolve表示a,b区间,往后推c位。解决:A.鲁棒性c%序列长. B通过reserve两块,在reserve整块,你会发现它里面的东西没动,只是两个大块交换了位置。
9.本题可以提升代码能力和二分思想,懒思想,如果你能完成它,说明你是很不错的。
10.感谢您的收看,要问我的语言为什么像个老先生一样咿咿呀呀,其实不是,只是这些东西难以搞好,而我提个醒罢了。
11.以下就是我的代码了,您可以充分批判,待写完这题之后,您一定能飞快写完的,不是吗?
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#define M 100001*2
#define INF 0x7fffffff
using namespace std;
int siz[M], minv[M], addv[M], rev[M], sta[M];
int ch[M][2], fa[M], key[M], rab[M], y[M];
int root, add_, top, size, n;
bool cmp(int a,int b) {return (a==b);}
struct splay
{
void debug(int h, int dep)
{
if(ch[h][0]) debug(ch[h][0], dep+1);
if(ch[h][1]) debug(ch[h][1], dep+1);
}
void maintain(int h)
{
int l = ch[h][0], r = ch[h][1];
minv[h] = key[h];
if(l) minv[h] = min(minv[h], minv[l]);
if(r) minv[h] = min(minv[h], minv[r]);
//minv[h] = min(minv[h], key[h]);
siz[h] = siz[l] + siz[r] + 1;
}
void pushdown(int h)
{
int &l = ch[h][0], &r = ch[h][1];
if(addv[h])
{
if(l) addv[l] += addv[h], key[l] += addv[h], minv[l] += addv[h];
if(r) addv[r] += addv[h], key[r] += addv[h], minv[r] += addv[h];
addv[h] = 0;
}
if(rev[h])
{
if(l) rev[l] ^= 1;
if(r) rev[r] ^= 1;
swap(ch[h][0], ch[h][1]);
//swap(l, r);
rev[h] = 0;
}
}
void rotate(int h)
{
int f = fa[h], g = fa[f];
if(g) {int c = cmp(f, ch[g][1]); ch[g][c] = h;}
fa[f] = h; fa[h] = g;
int c = cmp(h, ch[f][1]);
fa[ch[h][!c]] = f;
ch[f][c] = ch[h][!c];
ch[h][!c] = f;
if(cmp(f,root)) root = h;
maintain(f);
maintain(h);
}
void push_road(int h)
{
int top;
sta[top = 1] = h;
while(fa[h]) {sta[++top] = fa[h]; h = fa[h]; }
for(int i=top; i>=1; --i) pushdown(sta[i]);
}
void draw(int h,int aim)
{
push_road(h);
//int Tcnt = 0;
//puts("");
//if(fa[h] == aim) printf("!");
while(fa[h]^aim)
{
int f = fa[h], g = fa[f];
//printf("%d",fa[h]);
if(g^aim) rotate(f);
rotate(h); //if(++Tcnt > 10) break;
}
maintain(h);
//puts("");
}
void newnode(int &h, int f, int key_)
{
if(top!=-1) h = rab[top--]; else h = ++size;
ch[h][0] = ch[h][1] = addv[h] = 0;
minv[h] = key[h] = key_; fa[h] = f;
rev[h] = 0; siz[h] = 1;
}
void built(int &x, int L, int R, int f)
{
if(L <= R)
{
int MI = (L + R) >> 1;
newnode(x, f, y[MI]);
built(ch[x][0], L, MI-1, x);
built(ch[x][1], MI+1, R, x);
maintain(x);
}
}
void init()
{
root = 0; top = -1; size = 0;
minv[0] = key[0] = INF; ch[0][0] = ch[0][1] = 0;
siz[0] = 0; rev[0] = 0; addv[0] = 0; fa[0] = 0;
newnode(root, 0, INF);
newnode(ch[root][1], root, INF);
//printf("%d\n",size);
built(ch[ch[root][1]][0], 1, n, ch[root][1]);
maintain(ch[root][1]);
maintain(root);
}
int id(int k)
{
int h;
pushdown(root);
for(h = root; siz[ch[h][0]] + 1 != k;)
{
if(siz[ch[h][0]] + 1 > k) h = ch[h][0];
else {k -= (siz[ch[h][0]] + 1); h = ch[h][1];}
pushdown(h);
}
return h;
}
int getmin(int a,int b)
{
int x = id(a-1);
int y = id(b+1);
draw(x, 0);
draw(y, x);
int w = ch[y][0];
maintain(y);
maintain(x);
return minv[w];
}
void insert(int a,int key)
{
int x = id(a);
int y = id(a+1);
draw(x, 0);
draw(y, x);
newnode(ch[y][0], y, key);
maintain(y);
maintain(x);
}
void del(int a)
{
int x = id(a-1);
int y = id(a+1);
draw(x, 0);
draw(y, x);
int w = ch[y][0];
rab[++top] = w;
ch[y][0] = 0;
//w = 0;
maintain(y);
maintain(x);
}
//void debug();
void add(int a,int b,int key_)
{
int x = id(a-1);
int y = id(b+1);
draw(x, 0);
draw(y, x);
int w = ch[y][0];
addv[w] += key_;
key[w] += key_;
minv[w] += key_;
maintain(y);
maintain(x);
}
void reserve(int a,int b)
{
int x = id(a-1);
int y = id(b+1);
draw(x, 0);
draw(y, x);
int w = ch[y][0];
rev[w] ^= 1;
}
void revolve(int a,int b,int t)
{
int w = b - a + 1;
t %= w;
if(t < 0) t += w;
if(t)
{
reserve(a, b-t);
reserve(b-t+1,b);
reserve(a,b);
}
}
} tree;
int u(int &x) {++x;}
inline void read(int &x)
{
x = 0;
int ta = 1;
char ch = getchar(); if(ch == '-') ta = -1;
while(ch > '9' || ch < '0') {ch = getchar(); if(ch == '-') ta = -1;}
while(ch >= '0'&& ch <='9') x = x * 10 + ch - '0', ch = getchar();
x *= ta;
}
int main()
{
char cmd[20]; int q, val, x, yx;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(scanf("%d",&n) == 1)
{
for(int i=1; i<=n; ++i) read(y[i]);///scanf("%d",&y[i]);
//for(int i=1; i<=n; ++i) printf("%d ",y[i]);
tree.init();
///scanf("%d",&q);
read(q);
//tree.debug(root, 0);
//printf("%d",q);
//return 0;
while(q--)
{
scanf("%s",cmd);
if(strcmp(cmd,"ADD") == 0)
{
//scanf("%d%d%d",&x,&yx,&val);
read(x), read(yx), read(val);
//printf("%d",val);
tree.add(x+1,yx+1,val);
}
if(strcmp(cmd,"REVERSE") == 0)
{
//scanf("%d%d",&x,&yx);
read(x), read(yx);
tree.reserve(x+1,yx+1);
}
if(strcmp(cmd,"REVOLVE") == 0)
{
//scanf("%d%d%d",&x,&yx,&val);
read(x), read(yx), read(val);
tree.revolve(x+1,yx+1,val);
}
if(strcmp(cmd,"INSERT") == 0)
{
//scanf("%d%d",&x,&val);
read(x), read(val);
tree.insert(x+1,val);
}
if(strcmp(cmd,"DELETE") == 0)
{
//scanf("%d",&x);
read(x);
tree.del(x+1);
}
if(strcmp(cmd,"MIN") == 0)
{
//scanf("%d%d",&x,&yx);
read(x), read(yx);
printf("%d\n",tree.getmin(x+1,yx+1));
}
}
}
}
作者:不知到本文的帮助价值,-_-, sad story.
更多推荐
序列神器伸展树 区间维护,区间提取,区间翻转的AC模板。
发布评论