记录编号	61438	评测结果	MMMMMMMMMM
题目名称	[NOI 2005]维护数列	最终得分	0
用户昵称	宋S	是否通过	未通过
代码语言	C++	运行时间	0.000 s
提交时间	2013-06-10 10:37:02	内存使用	0.00 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define inf 2147483647
#define lch(x) tree[x].son[0]
#define rch(x) tree[x].son[1]
#define fa(x) tree[x].fa
#define data(x) tree[x].data
#define size(x) tree[x].size
#define sum(x) tree[x].sum
#define lmax(x) tree[x].lmax
#define rmax(x) tree[x].rmax
#define maxx(x) tree[x].max
#define flag(x) tree[x].flag
#define lazy(x) tree[x].lazy
#define setc(y,d,x) fa(tree[y].son[d]=x)=y
using namespace std;
typedef struct
{
    int son[2],fa,data;
    int size,sum,lmax,rmax,max;
    int flag,lazy;
}node;
node tree[4100000];
int a[4100000];
int n,m,tot,root,root2;
char s[10];
char ss[6]={'S','L','K','V','T','X'};

inline int up(int x)
{
    size(x)=size(lch(x))+size(rch(x))+1;
    sum(x)=sum(lch(x))+sum(rch(x))+data(x);
    lmax(x)=max(lmax(lch(x)),sum(lch(x))+data(x)+max(0,lmax(rch(x))));
    rmax(x)=max(rmax(rch(x)),sum(rch(x))+data(x)+max(0,rmax(lch(x))));
    maxx(x)=max(max(maxx(lch(x)),maxx(rch(x))),max(0,rmax(lch(x)))+data(x)+max(0,lmax(rch(x))));
    return x;
}

inline void put_flag(int x)
{
    swap(lch(x),rch(x));
    swap(lmax(x),rmax(x));
    flag(x)^=1;
}

inline void put_lazy(int x,int d)
{
    lazy(x)=data(x)=d;
    sum(x)=size(x)*d;
    lmax(x)=rmax(x)=maxx(x)=max(d,sum(x));
}

inline void down(int x)
{
    if (flag(x))
        {
            if (lch(x)) put_flag(lch(x));
            if (rch(x)) put_flag(rch(x));
            flag(x)=0;
        }
    if (lazy(x)!=inf)
        {
            if (lch(x)) put_lazy(lch(x),lazy(x));
            if (rch(x)) put_lazy(rch(x),lazy(x));
            lazy(x)=inf;
        }
}

inline void rotate(int x)
{
    int y=fa(x),z=fa(y),d=(x==rch(y));
    down(y); down(x);
    fa(x)=z;
    if (z) tree[z].son[y==rch(z)]=x;
    setc(y,d,tree[x].son[!d]);
    setc(x,!d,up(y));
}

inline int splay(int x,int s)
{
    for (;fa(x)!=s;rotate(x))   
        if (fa(fa(x))!=s)
            rotate((x==rch(fa(x)))==(fa(x)==rch(fa(fa(x))))?fa(x):x);
    return up(x);
}

inline int find(int k)
{
    for (int x=root,sum=0;down(x),1;x=(size(lch(x))+sum<k)?sum+=size(lch(x))+1,rch(x):lch(x))
        if (size(lch(x))+sum+1==k) return x;
}

int treebuild(int fa,int l,int r)
{
    if (l>r) return 0;
    int mid=(l+r)>>1;
    fa(mid)=fa;
    data(mid)=a[mid-1];
    lazy(mid)=inf;
    lch(mid)=treebuild(mid,l,mid-1);
    rch(mid)=treebuild(mid,mid+1,r);
    return up(mid);
}

inline void part(int l,int r)
{
    l=find(l-1); r=find(r+1);
    root=splay(l,0);
    splay(r,l);
}

inline void init()
{
    scanf("%d %d",&n,&m);
    for (int i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    lazy(0)=inf;
    lmax(0)=rmax(0)=maxx(0)=-inf;
    root=treebuild(0,1,n+2);
    tot=n+2;
}

inline int get()
{
    scanf("%s",&s);
    for (int i=0; i<6; ++i)
        if (s[2]==ss[i]) return i+1;
}

inline void work()
{
    int l,r,c,k;
    while (m--)
        {
            k=get();
            if (k==1)
                {
                    scanf("%d %d",&l,&r);
                    n+=r;
                    for (int i=1; i<=r; ++i)
                        scanf("%d",&a[++tot]);
                    root2=treebuild(0,tot-r+2,tot+1);
                    if (!l)
                        {
                            root=splay(find(2),0);
                            setc(lch(root),1,root2);
                            root=splay(lch(root),0);
                        }else
                        {
                            part(l+1,l+1);
                            down(lch(rch(root)));
                            setc(lch(rch(root)),1,root2);
                            root=splay(lch(rch(root)),0);
                        }
                }
            if (k==2)
                {
                    scanf("%d %d",&l,&r);
                    n-=r;
                    r=l+r-1;
                    part(l+1,r+1);
                    lch(rch(root))=0;
                    root=splay(rch(root),0);
                }
            if (k==3)
                {
                    scanf("%d %d %d",&l,&r,&c);
                    r=l+r-1;
                    part(l+1,r+1);
                    put_lazy(lch(rch(root)),c);
                    root=splay(lch(rch(root)),0);
                }
            if (k==4)
                {
                    scanf("%d %d",&l,&r);
                    r=l+r-1;
                    part(l+1,r+1);
                    put_flag(lch(rch(root)));
                    root=splay(lch(rch(root)),0);
                }
            if (k==5)
                {
                    scanf("%d %d",&l,&r);
                    r=l+r-1;
                    part(l+1,r+1);
                    printf("%d\n",sum(lch(rch(root))));
                }
            if (k==6)
                {
                    part(2,n+1);
                    printf("%d\n",maxx(lch(rch(root))));
                }
        }
}

int main()
{
    freopen("seq2005.in","r",stdin);
    freopen("seq2005.out","w",stdout);
    init();
    work();
    return 0;
}