【fhq Treap】bzoj1500（听说此题多码上几遍就能不惧任何平衡树题）

1500: [NOI2005]维修数列

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 15112 Solved: 4996
[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

题解

非常恶心的一道题。。。

用fhq Treap完成的话

1、把原有的平衡树从pos处拆开，把新加的点新建一颗小平衡树合并进去

2、把原有平衡树从pos和pos+num处拆开，合并左右中间不要【但是记得回收下标】

3、把原有平衡树从pos和pos+num处拆开，在中间打上标记cov

4、把原有平衡树从pos和pos+num处拆开，在中间打上标记mark

5、把原有平衡树从pos和pos+num处拆开，输出sum[中间]

6、输出ma[rt];

【注意fhq Treap的lazy标记和线段树的不一样，线段树的标记是标而不改，fhq Treap是标时即改，不然在split和merge时可能不会改变之前标记的根节点】

注：spli是我校大神，用函数名调戏一下他hhh

代码

//by 减维

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<map>

#include<bitset>

#include<algorithm>

#define inf 1<<30

#define ll long long

using namespace std;

int n,m,rt,sz,siz[],son[][],val[],lm[],rm[],ma[],sum[],mark[],cov[],pri[];

int a[];

char ch[];

queue<int>q;

int newnode(int v)

{

    int x;

    if(!q.empty())

        x=q.front(),q.pop();

    else x=++sz;

    siz[x]=;

    son[x][]=son[x][]=mark[x]=;

    cov[x]=inf;pri[x]=rand();

    val[x]=sum[x]=ma[x]=v;

    lm[x]=rm[x]=v;

    return x;

}

void upda(int x)

{

    if(!x)return ;

    siz[x]=siz[son[x][]]+siz[son[x][]]+;

    sum[x]=sum[son[x][]]+sum[son[x][]]+val[x];

    ma[x]=max(max(,rm[son[x][]])+val[x]+max(,lm[son[x][]]),max(ma[son[x][]],ma[son[x][]]));

    lm[x]=max(lm[son[x][]],sum[son[x][]]+val[x]+max(,lm[son[x][]]));

    rm[x]=max(rm[son[x][]],sum[son[x][]]+val[x]+max(,rm[son[x][]]));

}

void covered(int x,int v)

{

    val[x]=v;

    sum[x]=siz[x]*v;

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

    ma[x]=max(sum[x],val[x]);

    cov[x]=v;

}

void zhuan(int now)

{

    swap(son[now][],son[now][]);

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

    mark[now]^=;

}

void pd(int now)

{

    if(mark[now]){

        if(son[now][])zhuan(son[now][]);

        if(son[now][])zhuan(son[now][]);

    }

    if(cov[now]!=inf){

        if(son[now][])covered(son[now][],cov[now]);

        if(son[now][])covered(son[now][],cov[now]);

    }

    mark[now]=;cov[now]=inf;

}

int build(int l,int r)

{

    if(l>r)return ;

    int mid=(l+r)>>,v=a[mid];

    int now=newnode(v);

    son[now][]=build(l,mid-);

    son[now][]=build(mid+,r);

    upda(now);

    return now;

}

void dfs(int now)

{

    if(!now)return;

    dfs(son[now][]);

    printf("%d ",val[now]);

    dfs(son[now][]);

}

void spli(int now,int k,int &x,int &y)

{

    if(!now)x=y=;

    else{

        pd(now);

        if(k<=siz[son[now][]])

            y=now,spli(son[now][],k,x,son[now][]);

        else

            x=now,spli(son[now][],k-siz[son[now][]]-,son[now][],y);

        upda(now);

    }

}

int merge(int x,int y)

{

    if(!x||!y)return x+y;

    pd(x),pd(y);

    if(pri[x]<pri[y])

    {

        son[x][]=merge(son[x][],y);

        upda(x);

        return x;

    }else{

        son[y][]=merge(x,son[y][]);

        upda(y);

        return y;

    }

}

void rudui(int x)

{

    if(!x)return ;

    q.push(x);

    rudui(son[x][]);

    rudui(son[x][]);

}

int main()

{

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

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

    sum[]=siz[]=mark[]=cov[]=;

    ma[]=val[]=-inf;

    rt=build(,n);

    int pos,num,x,y,z,k,b,c,d;

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

    {

        //dfs(rt);printf("\n");

        scanf("%s",ch+);

        if (ch[]=='I'){

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

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

            z=build(,num);

            spli(rt,pos,x,y);

            rt=merge(merge(x,z),y);

        }else if (ch[]=='D'){

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

            spli(rt,pos-,x,y);

            spli(y,num,b,c);

            rt=merge(x,c);

            rudui(b);//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

        }else if (ch[]=='M' && ch[] =='K'){

            scanf("%d%d%d",&pos,&num,&k);

            spli(rt,pos-,x,y);

            spli(y,num,b,c);

            covered(b,k);

            rt=merge(x,merge(b,c));

        }else if (ch[]=='R'){

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

            spli(rt,pos-,x,y);

            spli(y,num,b,c);

            zhuan(b);

            rt=merge(x,merge(b,c));

        }else if (ch[]=='G'){

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

            spli(rt,pos-,x,y);

            spli(y,num,b,c);

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

            rt=merge(x,merge(b,c));

        }else{

            printf("%d\n",ma[rt]);

        }

    }

    return ;

}

巴特西