BZOJ1500 || 洛谷P2042 [NOI2005]维护数列【Splay】

Time Limit: 10 Sec
Memory Limit: 64 MB

Description

请写一个程序，要求维护一个数列，支持以下 6 种操作：
请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格

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操作，向输出文件依次打印结果，每个答案（数字）占一行。

题目分析

Splay支持的操作几乎全在这了
甚至还要写空间回收，当然你写指针当我没说
码了两百行才完

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
 
int read()
{
    int x=0,f=1;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}
 
const int maxn=1000010;
int n,m,cnt,rt;
int a[maxn],val[maxn];
int fa[maxn],ch[maxn][2],sum[maxn];
int lzy[maxn],sett[maxn],size[maxn];
int mx[maxn],lx[maxn],rx[maxn];
char ss[10];
queue<int> q;
 
void update(int x)
{
    int lc=ch[x][0],rc=ch[x][1];
    size[x]=size[lc]+size[rc]+1;
    sum[x]=sum[lc]+sum[rc]+val[x];
    lx[x]=max(lx[lc],sum[lc]+lx[rc]+val[x]);
    rx[x]=max(rx[rc],sum[rc]+rx[lc]+val[x]);
    mx[x]=max(max(mx[lc],mx[rc]),rx[lc]+lx[rc]+val[x]);
}
 
void push(int x)
{
    int lc=ch[x][0],rc=ch[x][1];
    if(sett[x])
    {
        sett[lc]=sett[rc]=1;
        val[lc]=val[rc]=val[x];
        sum[lc]=size[lc]*val[x]; sum[rc]=size[rc]*val[x];
        if(val[x]>=0)
        {
            lx[lc]=rx[lc]=mx[lc]=sum[lc];
            lx[rc]=rx[rc]=mx[rc]=sum[rc];
        }
        else
        {
            lx[lc]=rx[lc]=0; mx[lc]=val[x];
            lx[rc]=rx[rc]=0; mx[rc]=val[x];
        }
        sett[x]=lzy[x]=0;//全部置为一个数翻转也就没有意义了
    }
    if(lzy[x])
    {
        lzy[lc]^=1; lzy[rc]^=1;
        swap(lx[lc],rx[lc]); swap(lx[rc],rx[rc]);
        swap(ch[lc][0],ch[lc][1]); swap(ch[rc][0],ch[rc][1]);
        lzy[x]=0;
    }
}
 
int new_node(int p,int ff,int v,int num)
{
    int tt;
    if(!q.empty()) tt=q.front(),q.pop();
    else tt=++cnt;
    val[tt]=v; fa[tt]=num; ch[num][p>=ff]=tt;
    return tt;
}
 
void build(int p,int ll,int rr,int num)
{
    if(ll>rr) return;
    int mid=ll+rr>>1;
    int tt=new_node(mid,p,a[mid],num);
    if(ll==rr)
    {
        mx[tt]=sum[tt]=a[mid];
        lzy[tt]=sett[tt]=0;
        lx[tt]=rx[tt]=max(a[mid],0);
        size[tt]=1;
    }
    build(mid,ll,mid-1,tt); build(mid,mid+1,rr,tt);
    update(tt);
}
 
void rotate(int &p,int x)
{
    int y=fa[x],z=fa[y];
    int d=(ch[y][0]==x);
    if(y==p) p=x;
    else if(ch[z][0]==y) ch[z][0]=x;
    else ch[z][1]=x;
    fa[y]=x; fa[ch[x][d]]=y; fa[x]=z;
    ch[y][d^1]=ch[x][d]; ch[x][d]=y;
    update(y); update(x);
}
 
void splay(int &p,int x)
{
    while(x!=p)
    {
        int y=fa[x],z=fa[y];
        if(y!=p)
        {
            if((ch[z][0]==y)^(ch[y][0]==x))rotate(p,x);
            else rotate(p,y);
        }
        rotate(p,x);
    }
}
 
 
int find(int p,int k) 
{ 
    push(p);  
    int ss=size[ch[p][0]]; 
    if(k==ss+1) return p;    
    else if(k<=ss) return find(ch[p][0],k);
    else return find(ch[p][1],k-ss-1);  
}
 
void ins()
{
    int k=read(),tot=read();
    for(int i=1;i<=tot;++i) a[i]=read();
    int x=find(rt,k+1); splay(rt,x);
    int y=find(rt,k+2); splay(ch[x][1],y);
     
    int tt;
    if(!q.empty()) tt=q.front();
    else tt=cnt+1;
    build(1+tot>>1,1,tot,0);
     
    fa[tt]=y; ch[y][0]=tt;
    update(y); update(x);
}
 
void rec(int x)
{
    if(!x) return;
    rec(ch[x][0]); rec(ch[x][1]);
    q.push(x);
    fa[x]=ch[x][0]=ch[x][1]=lzy[x]=sett[x]=0;
}
 
void del()
{
    int k=read(),tot=read();
    int x=find(rt,k); splay(rt,x);
    int y=find(rt,k+tot+1); splay(ch[x][1],y);
     
    int tt=ch[y][0]; 
    fa[ch[y][0]]=ch[y][0]=0; rec(tt);
    update(y); update(x);
}
 
void qsum()
{
    int k=read(),tot=read();
    int x=find(rt,k); splay(rt,x);
    int y=find(rt,k+tot+1); splay(ch[x][1],y);
    printf("%d\n",sum[ch[y][0]]);
}
 
void rev()
{
    int k=read(),tot=read();
    int x=find(rt,k); splay(rt,x);
    int y=find(rt,k+tot+1); splay(ch[x][1],y);
     
    int z=ch[y][0];
    lzy[z]^=1;
    swap(ch[z][0],ch[z][1]);
    swap(lx[z],rx[z]);
    update(y); update(x);
}
 
void mks()
{
    int k=read(),tot=read(),v=read();
    int x=find(rt,k); splay(rt,x);
    int y=find(rt,k+tot+1); splay(ch[x][1],y);
     
    int z=ch[y][0];
    val[z]=v; sett[z]=1;
    sum[z]=size[z]*v;
    if(v>=0) lx[z]=rx[z]=mx[z]=sum[z];
    else lx[z]=rx[z]=0,mx[z]=v;
    update(y); update(x);
}
 
int main()
{
    n=read();m=read();
    mx[0]=a[1]=a[n+2]=-1e9;
    for(int i=2;i<=n+1;++i) a[i]=read();
     
    rt=1;
    build(n+3>>1,1,n+2,0);
     
    while(m--)
    {
        scanf("%s",&ss);
        if(ss[0]=='I') ins();
        else if(ss[0]=='D') del();
        else if(ss[0]=='G') qsum();
        else if(ss[0]=='R') rev();
        else if(ss[0]=='M'&&ss[2]=='K') mks();
        else if(ss[0]=='M'&&ss[2]=='X') printf("%d\n",mx[rt]);
    }
    return 0;
}