Gnarly Cow We are continually faced with a series of great opportunities brilliantly disguised as insoluble problems.

此题可以说是NOI历史上最繁杂的数据结构题目之一。出题者周源给出的标准解法为块状链表，他的标程长达11.3KB之多！块状链表虽然可以完美解决此题，但是其代码实现比较复杂，很容易出错。而Splay这种非常优美的数据结构可以巧妙地解决这道题，且其代码实现相对容易。

从零开始学习Splay，请参见sqybi的“The Magical Splay”。已经掌握Splay基础知识的，可以阅读zkw神牛的 《BST 拓展与伸展树(splay)一日通》 学习很多代码实现上的技巧，尤其是设立一个空结点null来避开一大堆繁杂的边界情况特殊判断。

此题用Splay的详细解法请参见BYVoid的解题报告 。我的代码大致与BYVoid的思路相符，但在插入操作时我并没有插成一条链，而是递归将要插入的子序列建成一颗比较平衡的子树。实际测试中，我的代码时间效率比较高，与块状链表标程的用时不相上下，甚至在极限大数据下比标程快。如果用fread快速读入方式，还可以节约近0.5s时间。

评测结果：
我的Splay代码
Start testing gnarlycow…
Compiling gnarlycow.sequence …
Success
Testing gnarlycow.sequence.1(sequence1.in)… Accepted 0.003s Score: 10
Testing gnarlycow.sequence.2(sequence2.in)… Accepted 0.007s Score: 10
Testing gnarlycow.sequence.3(sequence3.in)… Accepted 0.878s Score: 10
Testing gnarlycow.sequence.4(sequence4.in)… Accepted 0.149s Score: 10
Testing gnarlycow.sequence.5(sequence5.in)… Accepted 0.402s Score: 10
Testing gnarlycow.sequence.6(sequence6.in)… Accepted 0.780s Score: 10
Testing gnarlycow.sequence.7(sequence7.in)… Accepted 1.644s Score: 10
Testing gnarlycow.sequence.8(sequence8.in)… Accepted 1.590s Score: 10
Testing gnarlycow.sequence.9(sequence9.in)… Accepted 1.038s Score: 10
Testing gnarlycow.sequence.10(sequence10.in)… Accepted 1.190s Score: 10
Total score for gnarlycow.sequence : 100
块状链表标程：
Start testing standard…
Compiling standard.sequence …Success
Testing standard.sequence.1(sequence1.in)… Accepted 0.002s Score: 10
Testing standard.sequence.2(sequence2.in)… Accepted 0.010s Score: 10
Testing standard.sequence.3(sequence3.in)… Accepted 0.665s Score: 10
Testing standard.sequence.4(sequence4.in)… Accepted 0.362s Score: 10
Testing standard.sequence.5(sequence5.in)… Accepted 0.656s Score: 10
Testing standard.sequence.6(sequence6.in)… Accepted 0.931s Score: 10
Testing standard.sequence.7(sequence7.in)… Accepted 1.475s Score: 10
Testing standard.sequence.8(sequence8.in)… Accepted 1.879s Score: 10
Testing standard.sequence.9(sequence9.in)… Accepted 1.669s Score: 10
Testing standard.sequence.10(sequence10.in)… Accepted 1.778s Score: 10
Total score for standard.sequence : 100

/* Problem: NOI2005 Day1 sequence
 * Author: Li, Peiqian
 * Time: 2010.06.30
 * Status: AC
 * Tags: Splay
 */
#include 
#include 

using namespace std;

int num[500010],ptr=0,sptr=0;
struct node *null,*root,*s[500010],*q[500010];
struct node
{
	int value,size,sum,lmax,rmax,mmax;
	bool rev,same;
	node *c[2],*father;

	inline void reverse()
	{
		if(this==null) return;
		swap(c[0],c[1]);
		swap(lmax,rmax);
		rev=!rev;
	}

	inline void makesame(int v)
	{
		if(this==null) return;
		value=v;
		sum=v*size;
		lmax=rmax=mmax=max(sum,value);
		same=true;
	}

	inline void propagate()
	{
		if(this==null) return;
		if(rev)
		{
			c[0]->reverse();
			c[1]->reverse();
			rev=false;
		}
		if(same)
		{
			c[0]->makesame(value);
			c[1]->makesame(value);
			same=false;
		}
	}

	inline void update()
	{
		if(this==null) return;
		size=c[0]->size+c[1]->size+1;
		sum=c[0]->sum+c[1]->sum+value;
		lmax=max(c[0]->lmax,c[0]->sum+value+max(0,c[1]->lmax));
		rmax=max(c[1]->rmax,c[1]->sum+value+max(0,c[0]->rmax));
		mmax=max(c[0]->mmax,c[1]->mmax);
		mmax=max(mmax,max(0,c[0]->rmax)+value+max(0,c[1]->lmax));
	}

	inline void rotate(int o)//zig: o=0; zag: o=1;
	{
		node *t=father;
		t->propagate();
		propagate();
		t->c[!o]=c[o];
		father=t->father;
		if(c[o]!=null) c[o]->father=t;
		if(t->father!=null) t->father->c[t->father->c[1]==t]=this;
		t->father=this;
		c[o]=t;
		if(t==root) root=this;
		t->update();
	}

	inline void splay(node *goal)
	{
		for(propagate();father!=goal;)
			if(father->father==goal) rotate(father->c[0]==this);
			else
			{
				int o=(father->father->c[0]==father);
				if(father->c[!o]==this)
				{
					father->rotate(o);
					rotate(o);
				}
				else
				{
					rotate(!o);
					rotate(o);
				}
			}
		update();
	}

	inline void clear()
	{
		if(this==null) return;
		q[0]=this;
		for(int head=0,tail=1;headc[0]!=null) q[tail++]=q[head]->c[0];
			if(q[head]->c[1]!=null) q[tail++]=q[head]->c[1];
		}
	}
} tree[500010];

inline node* newnode(int x)
{
	node *p=sptr?s[--sptr]:tree+(ptr++);
	p->value=p->sum=p->lmax=p->rmax=p->mmax=x;
	p->size=1;
	p->father=p->c[0]=p->c[1]=null;
	p->rev=p->same=false;
	return p;
}

inline void select(int pos,node *goal)
{
	node *t=root;
	for(;;)
	{
		t->propagate();
		int m=t->c[0]->size;
		if(pos<=m) t=t->c[0];
		else if(pos==m+1) break;
		else
		{
			t=t->c[1];
			pos-=m+1;
		}
	}
	t->splay(goal);
}

node* maketree(int L,int R,node *f)
{
	if(L==R) return null;
	int M=(L+R)>>1;
	node *p=newnode(num[M]);
	p->c[0]=maketree(L,M,p);
	p->c[1]=maketree(M+1,R,p);
	p->father=f;
	p->update();
	return p;
}

inline void insertnum(int pos,int tot)
{
	for(int i=0;ic[1]->c[0]=maketree(0,tot,root->c[1]);
	root->c[1]->update();
	root->update();
}

int main()
{
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	int n,m,pos,tot,samevalue;
	char op[20];
	null=newnode(-1001);
	null->size=null->sum=0;
	root=newnode(-1001);
	root->c[1]=newnode(-1001);
	root->c[1]->father=root;
	root->update();
	scanf("%d%d",&n,&m);
	insertnum(0,n);
	for(;m;--m)
	{
		scanf("%s",op);
		if(op[2]!='X') scanf("%d%d",&pos,&tot);
		if(op[0]=='I') insertnum(pos,tot);
		else if(op[0]=='D')
		{
			select(pos,null);
			select(pos+tot+1,root);
			root->c[1]->c[0]->clear();
			root->c[1]->c[0]=null;
			root->c[1]->update();
			root->update();
		}
		else if(op[0]=='R')
		{
			select(pos,null);
			select(pos+tot+1,root);
			root->c[1]->c[0]->reverse();
			root->c[1]->update();
			root->update();
		}
		else if(op[0]=='G')
		{
			select(pos,null);
			select(pos+tot+1,root);
			printf("%d\n",root->c[1]->c[0]->sum);
		}
		else if(op[2]=='K')
		{
			select(pos,null);
			select(pos+tot+1,root);
			scanf("%d",&samevalue);
			root->c[1]->c[0]->makesame(samevalue);
			root->c[1]->update();
			root->update();
		}
		else printf("%d\n",root->mmax);
	}
	return 0;
}

这里附上块状链表标程：

{
            Program for NOI2005

                           written by Zhou Yuan
                                          2005.07.25
}
{$R-,Q-,S-}
Const
    InFile     = 'sequence.in';
    OutFile    = 'sequence.out';
    SegLen     = 800;
    LimitSave  = 2000;
    maximum    = maxlongint div 2;

Type
    Tcursor    = record
                     p , exec                : longint;
                 end;
    TSegment   = object
                     Len                     : longint;
                     data                    : array[1..SegLen] of longint;
                     sum , samevalue ,
                     InMax , next            : longint;
                     sideMax                 : array[false..true] of longint;
                     reversed , same         : boolean;
                     procedure init;
                     procedure fill;
                     procedure reverseit;
                     procedure Set_Interval(st , ed , c : longint);
                     procedure Set_Same(c : longint);
                     procedure maintain;
                     function Get_Sum(st , ed : longint) : longint;
                 end;
    Tmem       = object
                     open , closed           : longint;
                     free                    : array[1..LimitSave] of longint;
                     procedure init;
                     function _new : longint;
                     procedure _dispose(num : longint);
                 end;
    Tdata      = array[1..LimitSave] of TSegment;

Var
    mem        : Tmem;
    data       : Tdata;
    root , M   : longint;

procedure TSegment.init;
begin
    next := 0; Len := 0; same := false; reversed := false;
end;

procedure TSegment.fill;
var
    i          : longint;
begin
    if not same then exit;
    for i := 1 to Len do data[i] := samevalue;
    same := false;
end;

procedure TSegment.reverseit;
var
    i , tmp    : longint;
begin
    if not reversed then exit;
    if not same then
      for i := 1 to Len div 2 do
        begin
            tmp := data[i]; data[i] := data[Len - i + 1];
            data[Len - i + 1] := tmp;
        end;
    tmp := sidemax[false]; sidemax[false] := sidemax[true]; sidemax[true] := tmp;
    reversed := false;
end;

procedure TSegment.Set_Interval(st , ed , c : longint);
var
    i          : longint;
begin
    reverseit; fill;
    for i := st to ed do data[i] := c;
    maintain;
end;

procedure TSegment.Set_Same(c : longint);
begin
    same := true; samevalue := c;
    maintain;
end;

procedure TSegment.maintain;
var
    i , subsum : longint;
begin
    if same then
      begin
          if samevalue < 0 then InMax := samevalue else InMax := samevalue * Len;
          sum := samevalue * Len; sideMax[false] := InMax; sideMax[true] := InMax; exit;
      end;
    sum := 0; subsum := 0; InMax := data[1];
    for i := 1 to Len do
      begin
          subsum += data[i]; sum += data[i];
          if subsum > InMax then InMax := subsum;
          if subsum < 0 then subsum := 0;
      end;
    sideMax[false] := data[1]; subsum := 0;
    for i := 1 to Len do
      begin
          subsum += data[i];
          if subsum > sideMax[false] then sideMax[false] := subsum;
      end;
    sideMax[true] := data[Len]; subsum := 0;
    for i := Len downto 1 do
      begin
          subsum += data[i];
          if subsum > sideMax[true] then sideMax[true] := subsum;
      end;
end;

function TSegment.Get_Sum(st , ed : longint) : longint;
var
    tmp , i    : longint;
begin
    if same
      then exit(samevalue * (ed - st + 1))
      else begin
               if reversed then
                 begin tmp := Len - st + 1; st := Len - ed + 1; ed := tmp; end;
               tmp := 0;
               for i := st to ed do tmp += data[i];
               exit(tmp);
           end;
end;

procedure Tmem.init;
var
    i          : longint;
begin
    open := 1; closed := 0;
    for i := 1 to LimitSave do free[i] := i;
end;

function Tmem._new : longint;
begin
    if open = closed then
      begin assign(OUTPUT , ''); ReWrite(OUTPUT); writeln('ERROR'); Halt; end;
    _new := free[open]; open += 1; if open > LimitSave then open := 1;
end;

procedure Tmem._dispose(num : longint);
begin
    closed += 1; if closed > LimitSave then closed := 1;
    free[closed] := num;
end;

procedure init;
var
    i , p , N  : longint;
begin
    readln(N , M);
    mem.init; root := mem._new; data[root].Len := SegLen; p := root;
    for i := 1 to N do
      begin
          if data[p].Len = SegLen
            then begin
                     data[p].next := mem._new; data[p].maintain;
                     p := data[p].next; data[p].init;
                 end;
          data[p].Len += 1; read(data[p].data[data[p].Len]);
      end;
    readln;
    data[p].maintain;
end;

procedure Find(posi : longint; var p : Tcursor);
begin
    posi += SegLen; p.p := root;
    while posi > data[p.p].Len do
      begin
          posi -= data[p.p].Len;
          p.p := data[p.p].next;
      end;
    p.exec := posi;
end;

procedure Split(posi : longint; var p : longint);
var
    cursor     : Tcursor;
    i , tmp    : longint;
begin
    Find(posi , cursor);
    if cursor.exec <> data[cursor.p].Len
      then begin
               p := mem._new; data[p].init;
               data[p].next := data[cursor.p].next;
               data[cursor.p].next := p;
               data[cursor.p].reverseit;
               data[cursor.p].fill;
               for i := cursor.exec + 1 to data[cursor.p].Len do
                 begin
                     data[p].Len += 1;
                     data[p].data[data[p].Len] := data[cursor.p].data[i];
                 end;
               data[cursor.p].Len := cursor.exec; p := cursor.p;
               data[p].maintain; data[data[p].next].maintain;
           end
      else begin p := cursor.p; data[p].reverseit; data[p].fill; end;
end;

procedure Zip;
var
    i , j      : longint;
    last       : boolean;
begin
    i := root; last := false;
    while data[i].next <> 0 do
      if data[i].Len + data[data[i].next].Len <= SegLen
        then begin
                 if not last then begin data[i].fill; data[i].reverseit; end;
                 data[data[i].next].fill; data[data[i].next].reverseit;
                 for j := 1 to data[data[i].next].Len do
                   begin
                       data[i].Len += 1;
                       data[i].data[data[i].Len] := data[data[i].next].data[j];
                   end;
                 j := data[i].next; data[i].next := data[j].next;
                 mem._dispose(j); last := true;
             end
        else begin
                 if last then data[i].maintain;
                 i := data[i].next; last := false;
             end;
    if last then data[i].maintain;
end;

procedure Insert_Block;
var
    i , posi ,
    tot , p , tp
               : longint;
begin
    read(posi , tot); Split(posi , p);
    while tot > 0 do
      begin
          if data[p].Len = SegLen then
            begin
                data[p].maintain;
                tp := mem._new; data[tp].init; data[tp].next := data[p].next;
                data[p].next := tp; p := tp;
            end;
          data[p].Len += 1; read(data[p].data[data[p].Len]);
          tot -= 1;
      end;
    data[p].maintain;
    readln;
    Zip;
end;

procedure Delete_Block;
var
    i , posi , tot ,
    st , ed , t: longint;
begin
    readln(posi , tot); posi -= 1;
    Split(posi , st);
    Split(posi + tot , ed);
    repeat
      t := data[st].next; data[st].next := data[t].next;
      mem._dispose(t);
    until t = ed;
    Zip;
end;

procedure Make_Same;
var
    posi , c ,
    tot , t    : longint;
    st , ed    : Tcursor;
begin
    readln(posi , tot , c); posi -= 1;
    Find(posi , st); Find(posi + tot , ed);
    if st.p = ed.p
      then data[st.p].Set_Interval(st.exec + 1 , ed.exec , c)
      else begin
               data[st.p].Set_Interval(st.exec + 1 , data[st.p].Len , c);
               data[ed.p].Set_Interval(1 , ed.exec , c);
               t := st.p;
               while data[t].next <> ed.p do
                 begin
                     t := data[t].next;
                     data[t].Set_Same(c);
                 end;
           end;
end;

procedure Reverse_Block;
var
    sum , i ,
    posi , tot ,
    st , ed , t: longint;
    list       : array[1..LimitSave] of longint;
begin
    readln(posi , tot); posi -= 1;
    Split(posi , st); Split(posi + tot , ed);
    t := data[st].next; data[st].next := ed;
    sum := 1; list[1] := t;
    while t <> ed do
      begin t := data[t].next; sum += 1; list[sum] := t; end;
    for i := 1 to sum do data[list[i]].reversed := not data[list[i]].reversed;
    data[list[1]].next := data[ed].next;
    for i := sum downto 2 do data[list[i]].next := list[i - 1];
    Zip;
end;

procedure Get_Sum;
var
    posi , tot ,
    i , answer : longint;
    st , ed    : Tcursor;
begin
    readln(posi , tot); posi -= 1;
    Find(posi , st); Find(posi + tot , ed);
    if st.p = ed.p
      then answer := data[st.p].Get_Sum(st.exec + 1 , ed.exec)
      else begin
               answer := data[st.p].Get_Sum(st.exec + 1 , data[st.p].Len)
                       + data[ed.p].Get_Sum(1 , ed.exec);
               i := st.p;
               while data[i].next <> ed.p do
                 begin
                     i := data[i].next;
                     answer += data[i].sum;
                 end;
           end;
    writeln(answer);
end;

function fmax(a , b : longint) : longint;
begin
    if a > b then exit(a) else exit(b);
end;

procedure Get_MaxSum;
var
    answer , i ,
    last       : longint;
begin
    readln; answer := -maximum; last := -maximum;
    i := data[root].next;
    while i <> 0 do
      begin
          answer := fmax(answer , data[i].InMax);
          answer := fmax(answer , last + data[i].sideMax[data[i].reversed]);
          last := fmax(last + data[i].sum , data[i].sidemax[not data[i].reversed]);
          i := data[i].next;
      end;
    writeln(answer);
end;

procedure print_all;
var
    i , j      : longint;
begin
    i := root;
    while data[i].next <> 0 do
      begin
          i := data[i].next;
          if data[i].reversed
            then for j := data[i].Len downto 1 do
                   write(data[i].data[j] , ' ')
            else for j := 1 to data[i].Len do
                   write(data[i].data[j] , ' ');
      end;
    writeln;
end;

procedure workout;
var
    i          : longint;
    signal     : string[20];
    ch         : char;
begin
    for i := 1 to M do
      begin
          signal := ''; read(ch);
          while ch <> ' ' do
            begin signal += ch; if eoln then ch := ' ' else read(ch); end;
          if signal = 'INSERT' then Insert_Block;
          if signal = 'DELETE' then Delete_Block;
          if signal = 'MAKE-SAME' then make_Same;
          if signal = 'REVERSE' then Reverse_Block;
          if signal = 'GET-SUM' then Get_Sum;
          if signal = 'MAX-SUM' then Get_MaxSum;
//          print_all;
      end;
end;

Begin
    assign(INPUT , InFile); ReSet(INPUT);
    assign(OUTPUT , OutFile); ReWrite(OUTPUT);
      init;
      workout;
    Close(OUTPUT);
    Close(INPUT);
End.