【原题见这里
本题是Splay Tree处理序列问题(也就是当线段树用)的一个典型例题。

Splay Tree之所以可以当线段树用,是因为它可以支持一个序列,然后用“左端前趋伸展到根,右端后继伸展到根的右子结点,取根的右子结点的左子结点”这种伸展方法,对一个序列中的一整段进行整体操作。由于要防止出现前趋或后继不存在的情况,需要在这个序列的两端加入两个边界结点,要求其值不能影响到结点各种记载信息的维护(多取0、∞或-∞)。这两个边界结点在树中永远存在,不会被删除。

(1)结点的引用:
在当线段树用的Splay Tree中,真正的关键字是下标而不是值,因此,“序列中第i个结点”实际上对应的是“树中第(i+1)小的结点”(因为左边还有一个边界结点),这就说明在对结点引用时需要找第K小的操作。因此,下面的“结点x”指的是“树中第(x+1)小的结点”。
(2)标记:
在线段树中,如果对一个结点所表示的线段整体进行了某种操作,需要在这个结点上打上一个标记,在下一次再找到这个结点时,其标记就会下放到其两个子结点上。在Splay Tree中也可以引入标记。比如要对[2, 6]这一段进行整体操作,就将结点1伸展到根的位置,将结点7伸展到根的右子树的位置,然后结点7的左子树就表示[2, 6]这一段,对这棵子树的根结点打上标记并立即生效(必须是立即生效,而不是等下一次引用再生效),也就是立即改变该结点记录的一些信息的值。如果下次再次引用到这个结点,就要将其标记下放到其两个子结点处;
需要注意的一点是,如果要伸展某个结点x到r的子结点的位置,就必须保证从x原来的位置到r的这个子结点(x伸展后的位置)上的所有结点上均没有标记,否则就会导致标记混乱。因此,必须首先找到这个结点x,在此过程中不断下放标记。
(3)自底向上维护的信息:
标记可以看成一种自顶向下维护的信息。除了标记以外,作为“线段树”,往往还要维护一些自底向上维护的信息。比如在sequence这题中,就有lmax(左段连续最大和)、rmax(右段连续最大和)、midmax(全段连续最大和)以及sum(全段总和)等信息要维护。对于这类东东其实也很好办,因为子树大小(sz域)就是一种自底向上维护的信息,因此对于这些信息只要按照维护sz域的办法维护即可(统一写在upd函数里)。唯一的不同点是打标记时它们的值可能要改变。
(4)对连续插入的结点建树:
本题的插入不是一个一个插入,而是一下子插入一整段,因此需要先将它们建成一棵树。一般建树操作都是递归的,这里也一样。设目前要对A[l..r]建树(A为待插入序列),若l>r则退出,否则找到位于中间的元素mid = l + r >> 1,将A[mid]作根,再对A[l..mid-1]建左子树,对A[mid+1..r]建右子树即可。这样可以保证一开始建的就是一棵平衡树,减小常数因子。
(5)回收空间:
根据本题的数据范围提示,插入的结点总数最多可能达到4000000,但在任何时刻树中最多只有500002个结点(包括两个边界),此时为了节省空间,可以采用循环队列回收空间的方法。即:一开始将所有的可用空间(可用下标,本题为1~500002)存在循环队列Q里,同时设立头尾指针front和rear,每次如果有新结点插入,就取出Q[front]并作为新结点的下标,如果有结点要删除(本题是一次删除整棵子树,因此在删除后需要分别回收它们的空间),则从rear开始,将每个删除的结点的下标放回到Q里。当然,这种方法是要牺牲一定的时间的,因此在空间不是特别吃紧的情况下不要用。

【2012年1月16日更新】
今天重写sequence的时候,秃然发现加入的边界点可能会对lmax、rmax、midmax等的维护造成影响:当序列中所有的值都是负数时,若边界点的值设为0,将使这3个值也为0,所以,边界点的值应设为-INF(不会影响到sum,因为可以单独调出[l, r]的sum,避开边界)。这就说明并非所有这样的题中都可以设置边界点(比如HFTSC2011的那题就不行),如果边界点会对维护的信息造成影响,就不能设置边界点,在各个操作中,分4种情况判断。(代码已经修改)

下面上代码了:
#include <iostream>
#include 
<stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 500002, NOSM = -2000, INF = ~0U >> 2;
struct node {
    
int v, c[2], p, sz, sum, lmax, rmax, midmax, sm;
    
bool rev, d;
} T[MAXN 
+ 1];
int root, Q[MAXN + 1], front, rear, a[MAXN], len, res;
int max(int SS0, int SS1)
{
    
return SS0 >= SS1 ? SS0 : SS1;
}
int max(int SS0, int SS1, int SS2)
{
    
int M0 = SS0 >= SS1 ? SS0 : SS1; return M0 >= SS2 ? M0 : SS2;
}
void newnode(int n, int _v)
{
    T[n].v 
= T[n].sum = T[n].lmax = T[n].rmax = T[n].midmax = _v; T[n].c[0= T[n].c[1= 0; T[n].sz = 1; T[n].sm = NOSM; T[n].rev = 0;
}
void sc(int _p, int _c, bool _d)
{
    T[_p].c[_d] 
= _c; T[_c].p = _p; T[_c].d = _d;
}
void sm_opr(int x, int SM)
{
    T[x].sum 
= T[x].sz * SM;
    
if (SM > 0) T[x].lmax = T[x].rmax = T[x].midmax = T[x].sum; else T[x].lmax = T[x].rmax = T[x].midmax = SM;
}
void rev_opr(int x)
{
    
int c0 = T[x].c[0], c1 = T[x].c[1]; sc(x, c0, 1); sc(x, c1, 0);
    
int tmp = T[x].lmax; T[x].lmax = T[x].rmax; T[x].rmax = tmp;
}
void dm(int x)
{
    
int SM0 = T[x].sm;
    
if (SM0 != NOSM) {
        T[x].v 
= T[T[x].c[0]].sm = T[T[x].c[1]].sm = SM0; T[x].sm = NOSM;
        sm_opr(T[x].c[
0], SM0); sm_opr(T[x].c[1], SM0);
    }
    
if (T[x].rev) {
        T[T[x].c[
0]].rev = !T[T[x].c[0]].rev; T[T[x].c[1]].rev = !T[T[x].c[1]].rev; T[x].rev = 0;
        rev_opr(T[x].c[
0]); rev_opr(T[x].c[1]);
    }
}
void upd(int x)
{
    
int c0 = T[x].c[0], c1 = T[x].c[1];
    T[x].sz 
= T[c0].sz + T[c1].sz + 1;
    T[x].sum 
= T[c0].sum + T[c1].sum + T[x].v;
    T[x].lmax 
= max(T[c0].lmax, T[c0].sum + T[x].v + max(T[c1].lmax, 0));
    T[x].rmax 
= max(T[c1].rmax, max(T[c0].rmax, 0+ T[x].v + T[c1].sum);
    T[x].midmax 
= max(T[c0].midmax, T[c1].midmax, max(T[c0].rmax, 0+ T[x].v + max(T[c1].lmax, 0));
}
void rot(int x)
{
    
int y = T[x].p; bool d = T[x].d;
    
if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
    sc(y, T[x].c[
!d], d); sc(x, y, !d); upd(y);
}
void splay(int x, int r)
{
    
int p; while ((p = T[x].p) != r) if (T[p].p == r) rot(x); else if (T[x].d == T[p].d) {rot(p); rot(x);} else {rot(x); rot(x);} upd(x);
}
int Find_Kth(int K)
{
    
int i = root, S0;
    
while (i) {
        dm(i); S0 
= T[T[i].c[0]].sz + 1;
        
if (K == S0) breakelse if (K < S0) i = T[i].c[0]; else {K -= S0; i = T[i].c[1];}
    }
    
return i;
}
int mkt(int l, int r)
{
    
if (l > r) return 0;
    
int n0 = Q[front], mid = l + r >> 1if (front == MAXN) front = 1else front++;
    newnode(n0, a[mid]); 
int l_r = mkt(l, mid - 1), r_r = mkt(mid + 1, r);
    sc(n0, l_r, 
0); sc(n0, r_r, 1); upd(n0); return n0;
}
void ins(int pos)
{
    
int P0 = Find_Kth(pos); splay(P0, 0); int P1 = Find_Kth(pos + 1); splay(P1, root); sc(P1, mkt(0, len - 1), 0); upd(P1); upd(P0);
}
void era(int x)
{
    
if (!x) return;
    
if (rear == MAXN) rear = 1else rear++; Q[rear] = x;
    era(T[x].c[
0]); era(T[x].c[1]);
}
void del(int l, int r)
{
    
int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    
int root0 = T[P1].c[0]; sc(P1, 00); upd(P1); upd(P0); era(root0);
}
void mksame(int l, int r, int x)
{
    
int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    
int n = T[P1].c[0]; T[n].sm = x; sm_opr(n, x); upd(P1); upd(P0);
}
void reve(int l, int r)
{
    
int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    
int n = T[P1].c[0]; T[n].rev = !T[n].rev; rev_opr(n); upd(P1); upd(P0);
}
int get_sum(int l, int r)
{
    
int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root); 
    
int n = T[P1].c[0]; return T[n].sum;
}
int max_sum()
{
    
return T[root].midmax;
}
void prepare()
{
    T[
0].sz = T[0].sum = T[0].lmax = T[0].rmax = T[0].midmax = 0;
    front 
= 3; rear = MAXN; re1(i, MAXN) Q[i] = i;
    newnode(
1-INF); newnode(2-INF); sc(121); root = 1; T[root].p = 0;
}
int main()
{
    freopen(
"sequence.in""r", stdin);
    freopen(
"sequence.out""w", stdout);
    prepare();
    
int m, l, r, x;
    scanf(
"%d%d"&len, &m); char ch = getchar(), str[1000];
    re(i, len) scanf(
"%d"&a[i]); ins(1);
    re(i, m) {
        scanf(
"%s", str);
        
if (!strcmp(str, "INSERT")) {scanf("%d%d"&l, &len); re(i, len) scanf("%d"&a[i]); ins(++l);}
        
if (!strcmp(str, "DELETE")) {scanf("%d%d"&l, &r); r += l++; del(l, r);}
        
if (!strcmp(str, "MAKE-SAME")) {scanf("%d%d%d"&l, &r, &x); r += l++; mksame(l, r, x);}
        
if (!strcmp(str, "REVERSE")) {scanf("%d%d"&l, &r); r += l++; reve(l, r);}
        
if (!strcmp(str, "GET-SUM")) {scanf("%d%d"&l, &r); r += l++; printf("%d\n", get_sum(l, r));}
        
if (!strcmp(str, "MAX-SUM")) printf("%d\n", max_sum());
        ch 
= getchar();
    }
    fclose(stdin); fclose(stdout);
    
return 0;
}

最后把我的这个代码与BYVoid神犇的本题代码进行测试比较,结果(BYVoid神犇的代码见这里):

BYVoid神犇的:


本沙茶的:


【相关论文】
运用伸展树解决数列维护问题 by JZP
【感谢】
JZP神犇(提供论文)
BYVoid神犇(提供标程)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理