NOI 2005 維護數列

一點題外話:

這個題忒折磨人了,我寫了將近一天,兩頓飯沒吃。直到最後我下決心晚飯不吃我也要寫出來才搞出來。寫完後發現其實也不是很難,245行程序就搞定了。Splay真的不錯,反正我是懶得學塊狀鏈表了。

sequence

------------------------------------以下是題解------------------------------

這是NOI有史以來出過的最BT的數據結構題了,不少人寫的都是塊狀鏈表,我來個Splay的(比起編程難度,其實樸素纔是王道)。

建立一棵Splay,每個節點上要維護一下幾個信息:數值value,子樹大小size,子樹和sum,子數內和最大的子數列 maxsum,子樹區間內由左邊界能夠延伸的和最大子數列mls,子樹區間內由右邊界能夠延伸的和最大子數列mrs,以及兩個標記:子樹反轉標記rev,子樹同化標記same。爲了避免判斷邊界條件,首先插入兩個節點,作爲開頭和結尾,其永久排名分別爲1和當前數列長度。

插入和刪除操作和NOI2003的文本編輯器類似。插入一段數列,把第pos+1個元素splay到根節點,,把第pos+2個元素 splay到根節點的右子樹根節點,把要插入的這段數列建成一條鏈最好,然後把這個新建的鏈接到根節點右子樹的左子樹上,最後把鏈的尾splay到根節點。自底向上splay過程中要維護各項信息。

刪除就是把第pos個元素splay到根節點,把第pos+tot+1個元素splay到根節點的右子樹根節點,然後把根節點右子樹的左子樹直接砍掉就行了。由於數據規模比較大,如果內存比較緊張,要考慮回收空間。

考慮到修改和翻轉的區間可能很大,暴力的肯定不行。取得區間的方法和刪除一樣,然後我們就用標記標識代表這個區間的這棵子樹,今後訪問到這這棵子樹時,處理標記然後標記下傳。具體來說,下傳rev標記時,交換兩個子樹以及mls和mrs的值,然後兩棵子樹獲得標記。下傳same標記時,先把當前節點值傳給子節點,維護節點的sum值爲當前節點的value size。然後如果當前節點值爲非負數,令maxsum,mls,mrs的值爲value size,如果當前節點值爲負數,令maxsum,mls,mrs的值爲p->value。要注意的是,任何時候只要訪問到帶標記的節點,一定要標記下傳,尤其不要忘了在splay旋轉的時候。

另一個比較複雜的地方爲自底向上維護節點信息,我們有size,sum,mls,mrs,maxsum五個信息需要同時維護。其中size,sum比較簡單。

mls的取值有三種可能,直接繼承與左子樹的mls值,整個左子樹的sum + 當前節點value,以及左子樹的sum + 當前節點value + 右子樹的mls,取三者最大值。mrs類似於mls。

maxsum的維護更爲複雜,可能直接爲當前節點value,繼承左子樹的maxsum,繼承右子樹的maxsum,左子樹的mrs + 當前節點value,右子樹的mls + 當前節點value,以及左子樹的mrs + 右子樹的mls + 當前節點value,這五種情況,同樣取最大值。

有了上述的維護,求一段區間和也就不難了。同樣的方法找到待求和區間,直接讀取子樹根節點的sum值即可。求和最大的子數列直接讀取根節點的maxsum就行了。

看了zkw神牛的 《BST拓展與伸展樹(splay)一日通》,沒學會自頂向下的伸展樹,倒學了不少代碼技巧。例如建一個null節點,方便自底向上維護節點信息,還有空樹不好操作,那就插入兩個節點,作爲開頭和結尾。於是我的代碼僅僅245行(4.89K),比起許多塊狀鏈表簡單多了。

/* 
 * Problem: NOI2005 sequence
 * Author: Guo Jiabao
 * Time: 2009.5.30 14:19
 * State: Solved
 * Memo: 伸展樹
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=2850003,MAXL=500001,INF=1001;
struct SplayTree
{
    struct SplayNode
    {
        SplayNode *c[2],*f;
        int value,size,sum,maxsum,mls,mrs;
        bool rev,same;
    }*root,*null,*lb,*rb,SS[MAXN];
    int SC;
    SplayNode * NewNode(int value,SplayNode *f)
    {
        SplayNode *e=SS+ ++SC;
        e->value=value;
        e->size=1;e->f=f;
        e->sum=e->maxsum=e->mls=e->mrs=value;
        e->same=e->rev=false;
        e->c[0]=e->c[1]=null;
        return e;
    }
    inline int max(int a,int b){return a>b?a:b;}
    void update(SplayNode *p)
    {
        if (p==null) return;
        p->size = p->c[0]->size + p->c[1]->size + 1;
        p->sum = p->c[0]->sum + p->c[1]->sum + p->value;
        p->mls = p->c[0]->mls;
        p->mls = max( p->mls , p->c[0]->sum + p->value);
        p->mls = max( p->mls , p->c[0]->sum + p->value + p->c[1]->mls );
        p->mrs = p->c[1]->mrs;
        p->mrs = max( p->mrs , p->c[1]->sum + p->value);
        p->mrs = max( p->mrs , p->c[1]->sum + p->value + p->c[0]->mrs );
        p->maxsum = p->value;
        p->maxsum = max( p->maxsum , p->c[0]->maxsum );
        p->maxsum = max( p->maxsum , p->c[1]->maxsum );
        p->maxsum = max( p->maxsum , p->c[0]->mrs + p->value );
        p->maxsum = max( p->maxsum , p->c[1]->mls + p->value );
        p->maxsum = max( p->maxsum , p->c[0]->mrs + p->c[1]->mls + p->value );
    }
    void pushdown(SplayNode *p)
    {
        if (p==null) return;
        if (p->rev)
        {
            p->rev=false;
            SplayNode *q=p->c[0]; p->c[0]=p->c[1]; p->c[1]=q;
            p->c[0]->rev = !p->c[0]->rev;
            p->c[1]->rev = !p->c[1]->rev;
            int t=p->mls;
            p->mls=p->mrs; p->mrs=t;
        }
        if (p->same)
        {
            p->same=false;
            p->c[0]->same=p->c[1]->same=true;
            p->c[0]->value=p->c[1]->value=p->value;
            p->sum = p->maxsum = p->mls = p->mrs = p->value * p->size;
            if (p->value < 0)
                p->maxsum = p->mls = p->mrs = p->value;
        }
    }
    void rotate(SplayNode *x,int o)//Zig o=0 Zag o=1
    {
        SplayNode *y=x->f;
        pushdown(x->c[0]);
        pushdown(x->c[1]);
        pushdown(y->c[!o]);
        y->c[o] = x->c[!o];
        y->c[o]->f=y;
        x->f = y->f;
        if (y->f->c[0]==y)
            y->f->c[0]=x;
        else
            y->f->c[1]=x;
        y->f=x;
        x->c[!o]=y;
        update(y);
        update(x);
        if (root==y) root=x;
    }
    void splay(SplayNode *x,SplayNode *y)
    {
        pushdown(x);
        while (x->f!=y)
        {
            if (x->f->f==y)
            {
                if (x->f->c[0]==x)
                    rotate(x,0);
                else
                    rotate(x,1);
            }
            else if (x->f->f->c[0] == x->f)
            {
                if (x->f->c[0]==x)
                    rotate(x->f,0),rotate(x,0);
                else
                    rotate(x,1),rotate(x,0);
            }
            else
            {
                if (x->f->c[1]==x)
                    rotate(x->f,1),rotate(x,1);
                else
                    rotate(x,0),rotate(x,1);
            }
        }
    }
    void select(int k,SplayNode *y)
    {
        SplayNode *x=root;
        pushdown(x);
        for (;k != x->c[0]->size + 1;)
        {
            if (k <= x->c[0]->size)
                x=x->c[0];
            else
            {
                k-=x->c[0]->size + 1;
                x=x->c[1];
            }
            pushdown(x);
        }
        splay(x,y);
    }
    void Insert(int pos,int tot,int *C)
    {
        SplayNode *z,*t;
        z=t=NewNode(C[1],null);
        for (int i=2;i<=tot;i++)
            z=z->c[1]=NewNode(C[i],z);
        select(pos+1,null);
        select(pos+2,root);
        root->c[1]->c[0] = t;
        t->f=root->c[1];
        splay(z,null);
    }
    void Delete(int pos,int tot)
    {
        select(pos,null);
        select(pos+tot+1,root);
        root->c[1]->c[0] = null;
        splay(root->c[1],null);
    }
    void MakeSame(int pos,int tot,int value)
    {
        select(pos,null);
        select(pos+tot+1,root);
        root->c[1]->c[0]->same=true;
        root->c[1]->c[0]->value=value;
        splay(root->c[1]->c[0],null);
    }
    void Reverse(int pos,int tot)
    {
        select(pos,null);
        select(pos+tot+1,root);
        root->c[1]->c[0]->rev=!root->c[1]->c[0]->rev;
        splay(root->c[1]->c[0],null);
    }
    int GetSum(int pos,int tot)
    {
        select(pos,null);
        select(pos+tot+1,root);
        pushdown(root->c[1]->c[0]);
        return root->c[1]->c[0]->sum;
    }
    int MaxSum()
    {
        pushdown(root);
        update(root);
        return root->maxsum;
    }
    void init()
    {
        SC=-1;
        null=0;
        null=NewNode(-INF,0);
        null->size=0;
        lb=root=NewNode(-INF,null);
        rb=root->c[1]=NewNode(-INF,root);
        null->sum = lb->sum = rb->sum=0;
        update(root);
    }
}Splay;
int N,M,C[MAXL],pos,i,j,A;
char Ctrl[20];
int main()
{
    freopen("seq2005.in","r",stdin);
    freopen("seq2005.out","w",stdout);
    Splay.init();
    scanf("%d%d",&N,&M);
    for (i=1;i<=N;i++)
        scanf("%d",&C[i]);
    Splay.Insert(0,N,C);
    for (i=1;i<=M;i++)
    {
        scanf("%s",Ctrl);
        switch (Ctrl[0])
        {
            case 'I':
                scanf("%d%d",&pos,&N);
                for (j=1;j<=N;j++)
                    scanf("%d",&C[j]);
                Splay.Insert(pos,N,C);
                break;
            case 'D':
                scanf("%d%d",&pos,&N);
                Splay.Delete(pos,N);
                break;
            case 'R':
                scanf("%d%d",&pos,&N);
                Splay.Reverse(pos,N);
                break;
            case 'G':
                scanf("%d%d",&pos,&N);
                A=Splay.GetSum(pos,N);
                printf("%d\n",A);
                break;
            case 'M':
                if (Ctrl[2]=='K')
                {
                    scanf("%d%d%d",&pos,&N,&C[0]);
                    Splay.MakeSame(pos,N,C[0]);
                }
                else
                    printf("%d\n",Splay.MaxSum());
                break;
        }
    }
    return 0;
}
<h2><span class="mw-headline">維護數列 </span></h2>

【問題描述】

請寫一個程序,要求維護一個數列,支持以下 6 種操作:(請注意,格式欄 中的下劃線‘ _ ’表示實際輸入文件中的空格)

<table border="1" cellspacing="0" cellpadding="0">
<tbody>
<tr>
<td width="91" valign="top">操作編號</td>
<td width="217" valign="top">輸入文件中的格式</td>
<td width="276" valign="top">
<p align="center">說明</p>
</td>
</tr>
<tr>
<td width="91" valign="top">

1.     插入</td>
<td width="217" valign="top">

<span lang="EN-US">INSERT_<em>posi</em>_<em>tot</em>_<em>c</em>1_<em>c</em>2_..._<em>c</em></span><em><span lang="EN-US">tot</span></em></td>
<td width="276" valign="top"><span lang="EN-US">在當前數列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">個數字後插入 </span><em><span lang="EN-US">tot</span></em>

<span lang="EN-US">個數字:</span><em><span lang="EN-US">c</span></em><span lang="EN-US">1, <em>c</em>2, …, <em>c</em></span><em><span lang="EN-US">tot</span></em><span lang="EN-US">;若在數列首插</span>

<span lang="EN-US">入,則 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">爲 0</span></td>
</tr>
<tr>
<td width="91" valign="top">2.     刪除</td>
<td width="217" valign="top">

DELETE_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">從當前數列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">個數字開始連續</span>

<span lang="EN-US">刪除 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">個數字</span></td>
</tr>
<tr>
<td width="91" valign="top">3.     修改</td>
<td width="217" valign="top">

MAKE-SAME_<em>posi</em>_<em>tot</em>_<em>c</em></td>
<td width="276" valign="top"><span lang="EN-US">將當前數列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">個數字開始的連</span>

<span lang="EN-US">續 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">個數字統一修改爲 </span><em><span lang="EN-US">c</span></em></td>
</tr>
<tr>
<td width="91" valign="top">4.     翻轉</td>
<td width="217" valign="top">

REVERSE_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">取出從當前數列的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">個數字開始</span>

<span lang="EN-US">的 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">個數字,翻轉後放入原來的位置</span></td>
</tr>
<tr>
<td width="91" valign="top">5.     求和</td>
<td width="217" valign="top">

GET-SUM_<em>posi</em>_<em>tot</em></td>
<td width="276" valign="top"><span lang="EN-US">計算從當前數列開始的第 </span><em><span lang="EN-US">posi </span></em><span lang="EN-US">個數字</span>

<span lang="EN-US">開始的 </span><em><span lang="EN-US">tot </span></em><span lang="EN-US">個數字的和並輸出</span></td>
</tr>
<tr>
<td width="91" valign="top">6.     求和最

大的子列</td>
<td width="217" valign="top">

MAX-SUM</td>
<td width="276" valign="top">求出當前數列中和最大的一段子列,

並輸出最大和</td>
</tr>
</tbody></table>

【輸入格式】

輸入文件的第 1 行包含兩個數 N 和 M,N 表示初始時數列中數的個數,M表示要進行的操作數目。

第 2 行包含 N 個數字,描述初始時的數列。

以下 M 行,每行一條命令,格式參見問題描述中的表格。

【輸出格式】

對於輸入數據中的 GET-SUM 和 MAX-SUM 操作,向輸出文件依次打印結果,每個答案(數字)佔一行。

【輸入樣例】
<pre>9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM</pre>
【輸出樣例】
<pre>-1
10
1
10</pre>
【樣例說明】

初始時,我們擁有數列 2     -6     3      5      1     -5    -3     6      3

執行操作 GET-SUM 5 4,表示求出數列中從第 5 個數開始連續 4 個數字之和,1+(-5)+(-3)+6 = -1:
<pre>2     -6     3      5      1     -5    -3     6      3</pre>
執行操作 MAX-SUM,表示要求求出當前數列中最大的一段和,應爲 3+5+1+(-5)+(-3)+6+3 = 10:
<pre>2     -6     3      5      1     -5    -3     6      3</pre>
執行操作 INSERT 8 3 -5 7 2,即在數列中第 8 個數字後插入-5 7 2,
<pre>2     -6     3      5      1     -5    -3     6     -5     7      2      3</pre>
執行操作 DELETE 12 1,表示刪除第 12 個數字,即最後一個:
<pre>2     -6     3      5      1     -5    -3     6     -5     7      2</pre>
執行操作 MAKE-SAME 3 3 2,表示從第 3 個數開始的 3 個數字,統一修改爲 2:
<pre>2    -6    3    5    1    -5    -3    6    -5    7    2</pre>
改爲
<pre>2    -6    2    2    2    -5    -3    6    -5    7    2</pre>
執行操作 REVERSE 3 6,表示取出數列中從第 3 個數開始的連續 6 個數:
<pre>2           -6            2             2             2           -5            -3            6            -5            7            2</pre>
如上所示的灰色部分 2 2 2 -5 -3 6,翻轉後得到 6 -3 -5 2 2 2,並放回原來位置:
<pre>2     -6     6     -3     -5     2      2      2     -5     7      2</pre>
最後執行 GET-SUM 5 4 和 MAX-SUM,不難得到答案 1 和 10。
<pre>2            -6            6            -3            -5           2             2            2             -5           7             2</pre>
【評分方法】

本題設有部分分,對於每一個測試點:
  • 如果你的程序能在輸出文件正確的位置上打印 GET-SUM 操作的答案,你可以得到該測試點 60%的分數;
  • 如果你的程序能在輸出文件正確的位置上打印 MAX-SUM 操作的答案,你可以得到該測試點 40%的分數;
  • 以上兩條的分數可以疊加,即如果你的程序正確輸出所有 GET-SUM 和MAX-SUM 操作的答案,你可以得到該測試點 100%的分數。

    請注意:如果你的程序只能正確處理某一種操作,請確定在輸出文件正確的位置上打印結果,即必須爲另一種操作留下對應的行,否則我們不保證可以正確評分。

    【數據規模和約定】

  • 你可以認爲在任何時刻,數列中至少有 1 個數。

  • 輸入數據一定是正確的,即指定位置的數在數列中一定存在。
  • 50%的數據中,任何時刻數列中最多含有 30 000 個數;
  • 100%的數據中,任何時刻數列中最多含有 500 000 個數。
  • 100%的數據中,任何時刻數列中任何一個數字均在[-1 000, 1 000]內。
  • 100%的數據中,M ≤20 000,插入的數字總數不超過 4 000 000 個,輸入文件大小不超過 20MBytes。

相關日誌