bzoj1500

1500: [NOI2005]维修数列

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 12544 Solved: 3970
[Submit][Status][Discuss]

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。

Sample Input

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

Sample Output

-1
10
1
10

HINT

Source

打掉大boss了，一边抄一边写。

因为插入的数总共为4000000个，所以我们可以暴力地每个点直接插入，插入时，我们把新插入的元素建成一棵小树，再挂到大树上。

删除一样，转到那个节点，然后删除，但是这里要一个个删除，因为内存要循环利用。直接暴力删除，把节点放进一个栈中，用的时候拿出来，因为一共只有4000000个元素，绝对不会超时。

修改是打一个懒标记，tag[x]=c,然后pushdown即可。

翻转同上。

求和也是利用标记，sum[x]=sum[child[x][0]]+sum[child[x][1]]+key[x]

最后一个我们需要维护三个值，x节点表示的区间，lm[x]表示从x节点的区间最左端开始，最大的和是多少，rm[x]则是右边，mx[x]则表示这个节点的最大和

mx[x]=max(mx[child[x][0]],mx[child[x][1]],max(rm[child[x][0]],0)+key[x]+max(0,lm[child[x][1]])) 自己拿手画一下，想一下即可。

注意：pushdown要更新自己的sum[x],key[x]，然后也要把自己的儿子节点child[x][0],child[x][1]也更新掉，翻转也是，我不知道为什么，这里查了两个小时才发现。

makesame的初始值要设成-1001，因为更新的数在[-1000,1000]之间。

#include<cstdio>

#include<cstring>

#include<stack>

#include<vector>

using namespace std;

#define N 1000010

#define inf -1101

stack<int> s;

int n,m,root,cnt;

int size[N],child[N][],lm[N],rm[N],key[N],mx[N],sum[N];

int tag1[N],tag2[N],fa[N],a[N];

void update(int x)

{

    size[x]=size[child[x][]]+size[child[x][]]+;

    sum[x]=sum[child[x][]]+sum[child[x][]]+key[x];

    mx[x]=max(max(mx[child[x][]],mx[child[x][]]),

                    max(rm[child[x][]],)+key[x]+max(lm[child[x][]],));

    lm[x]=max(lm[child[x][]],sum[child[x][]]+key[x]+max(,lm[child[x][]]));

    rm[x]=max(rm[child[x][]],sum[child[x][]]+key[x]+max(,rm[child[x][]]));

}

void paint(int x)

{

    tag2[x]^=;

    swap(child[x][],child[x][]);

    swap(lm[x],rm[x]);

}

void paint(int x,int c)

{

    if(!x) return;

    tag1[x]=key[x]=c; sum[x]=size[x]*c;

    lm[x]=rm[x]=mx[x]=max(sum[x],key[x]);

}

void pushdown(int x)

{

    if(tag1[x]!=inf)

    {

        paint(child[x][],tag1[x]);//更新儿子节点

        paint(child[x][],tag1[x]);//更新儿子节点

        tag1[x]=inf;

    }

    if(tag2[x])

    {

        tag2[x]^=;

        if(child[x][]) paint(child[x][]);//更新儿子节点

        if(child[x][]) paint(child[x][]);//更新儿子节点

    }

}

void zig(int x)

{

    int y=fa[x];

    fa[x]=fa[y]; child[fa[x]][child[fa[x]][]==y]=x;

    child[y][]=child[x][];

    fa[child[x][]]=y;

    child[x][]=y; fa[y]=x;

    update(y); update(x);

}

void zag(int x)

{

    int y=fa[x];

    fa[x]=fa[y]; child[fa[x]][child[fa[x]][]==y]=x;

    child[y][]=child[x][];

    fa[child[x][]]=y;

    child[x][]=y; fa[y]=x;

    update(y); update(x);

}

void splay(int x,int t)

{

    while(fa[x]!=t)

    {

        pushdown(x);

        int y=fa[x],z=fa[y];

        if(z==t)

        {

            x==child[y][]?zig(x):zag(x); break;

        }

        x==child[y][]?zig(x):zag(x);

        x==child[z][]?zig(x):zag(x);

    }

    if(!t) root=x;

    update(root);

}

int find(int x,int rank)

{

    pushdown(x);

    if(size[child[x][]]+==rank) return x;

    if(size[child[x][]]>=rank) return find(child[x][],rank);

    else return find(child[x][],rank-size[child[x][]]-);

}

int newnode()

{

    int ret=;

    if(!s.empty())

    {

        ret=s.top();

        s.pop();

    } else ret=++cnt;

    return ret;

}

void build(int l,int r,int&x,int last)

{

    int mid=(l+r)>>;

    x=newnode(); key[x]=a[mid]; fa[x]=last;

    if(l<=mid-) build(l,mid-,child[x][],x);

    if(mid+<=r) build(mid+,r,child[x][],x);

    update(x);

}

void insert(int l,int r)

{

    int x=find(root,l),y=find(root,l+);//在l之后在l+1之前

    splay(x,); splay(y,root);

    for(int i=;i<=r-l+;i++) scanf("%d",&a[i]);

    build(,r-l+,child[child[root][]][],child[root][]);

    update(child[root][]); update(root);

}

void erase(int&x)

{

    if(!x) return;

    s.push(x);

    fa[x]=; key[x]=size[x]=sum[x]=tag2[x]=;

    tag1[x]=inf;

    lm[x]=rm[x]=mx[x]=-(<<);

    erase(child[x][]);

    erase(child[x][]);

    x=;

}

void del(int l,int r)

{

    int x=find(root,l-),y=find(root,r+);

    splay(x,); splay(y,root);

    erase(child[child[root][]][]);

    update(child[root][]); update(root);

}

void makesame(int l,int r,int c)

{

    int x=find(root,l-),y=find(root,r+);

    splay(x,); splay(y,root);

    paint(child[child[root][]][],c);//更新儿子节点

    update(child[root][]); update(root);

    splay(child[child[root][]][],);

}

void reverse(int l,int r)

{

    int x=find(root,l-),y=find(root,r+);

    splay(x,); splay(y,root);

    int b=child[child[root][]][];

    if(b) paint(b);//更新儿子节点

    splay(child[child[root][]][],);

}

void getsum(int l,int r)

{

    int x=find(root,l-),y=find(root,r+);

    splay(x,); splay(y,root);

    printf("%d\n",sum[child[child[root][]][]]);

}

void maxsum()

{

    printf("%d\n",mx[root]);

}

int main()

{

    for(int i=;i<=N;i++) tag1[i]=inf;

    scanf("%d%d",&n,&m);

    for(int i=;i<=n+;i++)

    {

        scanf("%d",&a[i]);

    }

    mx[]=mx[n+]=lm[]=lm[n+]=rm[]=rm[n+]=mx[]=

    lm[]=rm[]=a[]=a[n+]=-(<<);

    int x; build(,n+,x,);

    root=;

    while(m--)

    {

        char s[]; int pos,tot,c; scanf("%s",s);

        if(s[]=='S')

        {

            scanf("%d%d",&pos,&tot);

            insert(pos+,pos+tot);

        }

        if(s[]=='L')

        {

            scanf("%d%d",&pos,&tot);

            del(pos+,pos+tot);

        }

        if(s[]=='K')

        {

            scanf("%d%d%d",&pos,&tot,&c);

            if(tot>) makesame(pos+,pos+tot,c);

        }

        if(s[]=='V')

        {

            scanf("%d%d",&pos,&tot);

            reverse(pos+,pos+tot);

        }

        if(s[]=='T')

        {

            scanf("%d%d",&pos,&tot);

            getsum(pos+,pos+tot);

        }

        if(s[]=='X')

        {

            maxsum();

        }

    }

    return ;

}

巴特西