NOI 2005 維護數列
本文正體字版由OpenCC轉換
一點題外話：
這個題忒折磨人了，我寫了將近一天，兩頓飯沒喫。直到最後我下決心晚飯不喫我也要寫出來才搞出來。寫完後發現其實也不是很難，245行程序就搞定了。Splay真的不錯，反正我是懶得學塊狀鏈表了。
————————————以下是題解——————————
這是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。
上次修改時間 2017-05-22