内个我也不知道哪儿不对，TLE了，说说思路吧

其实思路也没什么说的，就是裸的splay，对于最后一个操作

我们记下每个区间的最长前缀，最长后缀，那么最长子序列就是

前缀，后缀，左子树的后缀+右子树的前缀+自己的值，里取max就行了

更新的时候前缀由左子树的前缀，左子树sum+右子树前缀转移

靠！！！！！！到底哪儿错了！！！！！TLE 你妹啊！！！！！

 

/**************************************************************    Problem: 1500    User: BLADEVIL    Language: Pascal    Result: Time_Limit_Exceed****************************************************************/ //By BLADEVILconst    sroot                   =-1;     var    n, m                    :int64;    a                       :array[-1..500010] of int64;    root                    :int64;    father, key, size       :array[-1..500010] of int64;    son                     :array[-1..500010,0..1] of int64;    flag                    :array[-1..500010] of boolean;    val, sum                :array[-1..500010] of int64;    pred, succ              :array[-1..500010] of int64;     procedure swap(var a,b:int64);var    c                       :int64;begin    c:=a; a:=b; b:=c;end;     function get_max(a,b:int64):int64;begin    if a>b then exit(a) else exit(b);end;     procedure update(x:int64);begin    if x=sroot then exit;    size[x]:=size[son[x,0]]+size[son[x,1]]+1;    sum[x]:=sum[son[x,0]]+sum[son[x,1]]+key[x];    pred[x]:=get_max(pred[son[x,0]],sum[son[x,0]]+pred[son[x,1]]+key[x]);    succ[x]:=get_max(succ[son[x,1]],sum[son[x,1]]+succ[son[x,0]]+key[x]);end; procedure c_renew(x,y:int64);begin    key[x]:=y; sum[x]:=size[x]*y;    pred[x]:=get_max(y,sum[x]);    succ[x]:=get_max(y,sum[x]);    val[x]:=y;end; procedure r_renew(x:int64);begin    swap(son[x,0],son[x,1]);    flag[x]:=not flag[x];end; procedure push_down(x:int64);var    l, r                    :int64;begin    l:=son[x,0]; r:=son[x,1];    if flag[x] then    begin        if l<>-1 then r_renew(l);        if r<>-1 then r_renew(r);        flag[x]:=false;    end;    if val[x]<>0 then    begin        if l<>-1 then c_renew(l,val[x]);        if r<>-1 then c_renew(r,val[x]);        val[x]:=0;    end;end;     function build(l,r:int64):int64;var    mid                     :int64;begin    mid:=(l+r) div 2;    key[mid]:=a[mid];    build:=mid;    if mid-1>=l then    begin        son[mid,0]:=build(l,mid-1);        father[son[mid,0]]:=mid;    end;    if mid+1<=r then    begin        son[mid,1]:=build(mid+1,r);        father[son[mid,1]]:=mid;    end;    update(mid);end; procedure rotate(x,y:int64);var    f                       :int64;begin    push_down(x);    f:=father[x];    son[f,y]:=son[x,y xor 1];    father[son[x,y xor 1]]:=f;    if f=root then root:=x else        if f=son[father[f],0] then            son[father[f],0]:=x else            son[father[f],1]:=x;    father[x]:=father[f];    father[f]:=x;    son[x,y xor 1]:=f;    update(f);    update(x);end; procedure splay(x,y:int64);var    u, v                    :int64;begin    while father[x]<>y do    if father[father[x]]=y then        rotate(x,ord(x=son[father[x],1]))    else    begin        if x=son[father[x],0] then u:=1 else u:=-1;        if father[x]=son[father[father[x]],0] then v:=1 else v:=-1;        if v*u=1 then        begin            rotate(father[x],ord(x=son[father[x],1]));            rotate(x,ord(x=son[father[x],1]));        end else        begin            rotate(x,ord(x=son[father[x],1]));            rotate(x,ord(x=son[father[x],1]));        end;    end;    update(x);end; function find(k:int64):int64;var    t                       :int64;begin    t:=root;    while true do    begin        push_down(t);        if size[son[t,0]]+1=k then exit(t);        if size[son[t,0]]+1>k then t:=son[t,0] else        begin            dec(k,size[son[t,0]]+1);            t:=son[t,1];        end;    end;end; procedure insert;var    i                       :longint;       l, s                    :int64;    p, q                    :int64;begin    read(l,s);    for i:=n+1 to n+s do read(a[i]);    readln;    q:=build(n+1,n+s);    n:=n+s;    p:=find(l+1); splay(p,sroot);    p:=find(l+2); splay(p,root);    p:=son[root,1];    father[q]:=p;    son[p,0]:=q;    update(p);    update(root);end; procedure delete;var    p                       :int64;    l, s                    :int64;begin    readln(l,s);    p:=find(l); splay(p,sroot);    p:=find(l+s+1); splay(p,root);    p:=son[son[root,1],0];    father[p]:=-1;    son[son[root,1],0]:=-1;    update(son[root,1]);    update(root);end; procedure change;var    l, s, c                 :int64;    p                       :int64;begin    readln(l,s,c);    p:=find(l); splay(p,sroot);    p:=find(l+s+1); splay(p,root);    p:=son[son[root,1],0];    c_renew(p,c);    update(son[root,1]);    update(root);end; procedure reverse;var    p                       :int64;    l, s                    :int64;begin    readln(l,s);    p:=find(l); splay(p,sroot);    p:=find(l+s+1); splay(p,root);    p:=son[son[root,1],0];    r_renew(p);    //update(son[root,1]);    //update(root);end;     procedure get_sum;var    l, s                    :int64;    p                       :int64;begin    readln(l,s);    p:=find(l); splay(p,sroot);    p:=find(l+s+1); splay(p,root);    p:=son[son[root,1],0];    writeln(sum[p]);end;     procedure max_sum;var    l, r                    :int64;begin    readln;    l:=son[root,0]; r:=son[root,1];    writeln(get_max(succ[l]+pred[r]+key[root],get_max(pred[l],succ[r])));end;     procedure main;var    i                       :longint;    ss                      :ansistring;    ch                      :char;begin    fillchar(son,sizeof(son),255);    read(n,m);    for i:=1 to n do read(a[i]);    inc(n);    root:=build(0,n);    father[root]:=sroot;    readln;    for i:=1 to m do    begin        read(ch);        ss:='';        while ch<>' ' do        begin            ss:=ss+ch;            read(ch);            if ss='MAX-SUM' then break;        end;        if ss='INSERT' then insert else        if ss='DELETE' then delete else        if ss='MAKE-SAME' then change else        if ss='REVERSE' then reverse else        if ss='GET-SUM' then get_sum else        if ss='MAX-SUM' then max_sum;    end;end; begin    main;end.