洛谷 P2042 [NOI2005]维护数列-Splay(插入 删除 修改 翻转 求和 最大的子序列)

因为要讲座，随便写一下，等讲完有时间好好写一篇splay的博客。

先直接上题目然后贴代码，具体讲解都写代码里了。

参考的博客等的链接都贴代码里了，有空再好好写。

P2042 [NOI2005]维护数列

题目描述

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

输入输出格式

输入格式：

输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M 表示要进行的操作数目。 第 2 行包含 N 个数字，描述初始时的数列。 以下 M 行，每行一条命令，格式参见问题描述中的表格

输出格式：

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

输入输出样例

输入样例#1： 复制

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

输出样例#1： 复制

-1
10
1
10

说明

你可以认为在任何时刻，数列中至少有 1 个数。

输入数据一定是正确的，即指定位置的数在数列中一定存在。

50%的数据中，任何时刻数列中最多含有 30 000 个数；

100%的数据中，任何时刻数列中最多含有 500 000 个数。

100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。

100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。

代码:

/*
https://www.luogu.org/problemnew/show/P2042
https://www.luogu.org/problemnew/solution/P2042
https://baijiahao.baidu.com/s?id=1613228134219334653&wfr=spider&for=pc
https://www.cnblogs.com/victorique/p/8478866.html
https://www.cnblogs.com/noip/archive/2013/05/31/3111169.html
https://baike.baidu.com/item/%E4%BC%B8%E5%B1%95%E6%A0%91/7003945?fr=aladdin
https://blog.csdn.net/changtao381/article/details/8936765
https://blog.csdn.net/huzujun/article/details/81394092
*/

//插入 删除 修改 翻转 求和 最大的子序列
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
const int inf=0x3f3f3f3f;

int n,m,rt,cnt;
int a[maxn],id[maxn],fa[maxn],tree[maxn][2];
int sum[maxn],sz[maxn],val[maxn],mx[maxn],lx[maxn],rx[maxn];
int tag[maxn],rev[maxn];
//tag 是否有统一修改的标记，rev 是否有统一翻转的标记

queue<int> q;

void pushup(int x)//分治，类似线段树的区间合并，但是因为当前节点也有值，所以要加上当前节点的val
{
    int l=tree[x][0],r=tree[x][1];
    sum[x]=sum[l]+sum[r]+val[x];
    sz[x]=sz[l]+sz[r]+1;
    lx[x]=max(lx[l],sum[l]+lx[r]+val[x]);
    rx[x]=max(rx[r],sum[r]+rx[l]+val[x]);
    mx[x]=max(max(mx[l],mx[r]),rx[l]+lx[r]+val[x]);//区间最大子段和
}

void pushdown(int x)
{
    int l=tree[x][0],r=tree[x][1];
    if(tag[x]){//有统一修改的标记，翻转就没有意义了
        rev[x]=tag[x]=0;
        if(l) tag[l]=1,val[l]=val[x],sum[l]=sz[l]*val[x];
        if(r) tag[r]=1,val[r]=val[x],sum[r]=sz[r]*val[x];
        if(val[x]>=0){
            if(l) lx[l]=rx[l]=mx[l]=sum[l];
            if(r) lx[r]=rx[r]=mx[r]=sum[r];
        }
        else{
            if(l) lx[l]=rx[l]=0,mx[l]=val[x];
            if(r) lx[r]=rx[r]=0,mx[r]=val[x];
        }
    }
    if(rev[x]){
        rev[x]=0;rev[l]^=1;rev[r]^=1;
        swap(lx[l],rx[l]);swap(lx[r],rx[r]);//注意，在翻转操作中，前后缀的最长上升子序列都反过来了，很容易错
        swap(tree[l][0],tree[l][1]);swap(tree[r][0],tree[r][1]);
    }
}

void rotate(int x,int &k)
{
    int y=fa[x],z=fa[y],l=(tree[y][1]==x),r=l^1;
    if(y==k) k=x;
    else tree[z][tree[z][1]==y]=x;
    fa[tree[x][r]]=y;fa[y]=x;fa[x]=z;//改变父子关系。爸爸变儿子，爷爷变爸爸
    tree[y][l]=tree[x][r];tree[x][r]=y;
    pushup(y);pushup(x);//旋转操作，改变关系之后标记上传
}

/*
伸展操作，三种状态：
1.x的爸爸y是目标状态，直接翻转x
2.x有爸爸y，有爷爷z，如果三点在一条直线上，就先翻转爸爸y，这样翻转是双旋，保持平衡(关于旋转 双旋、单旋，讲一下)
3.x有爸爸y，有爷爷z，三点不在一条直线上，直接翻转两次x就可以
*/
void splay(int x,int &k)//伸展操作，核心操作
{
    while(x!=k){//一直到转到目标状态
        int y=fa[x],z=fa[y];
        if(y!=k){//如果爸爸不是目标状态
            if((tree[z][0]==y)^(tree[y][0]==x)) rotate(x,k);//如果三点不在一条直线上，直接转自己
            else rotate(y,k);
        }
        rotate(x,k);
    }
}

/*
查找操作，核心操作之二
区间翻转和插入以及删除的操作都需要find操作
因为维护的区间的实际编号是不连续的，所以需要查找要操作的区间对应平衡树的中序遍历的那段区间
*/
int find(int x,int rk)//找排名第rk的
{
    pushdown(x);//因为所有操作都是需要find，所以在这里标记下传就可以
    int l=tree[x][0],r=tree[x][1];
    if(sz[l]+1==rk) return x;//就是二叉树的搜索操作
    if(sz[l]  >=rk) return find(l,rk);
    else return find(r,rk-sz[l]-1);

}

/*
这道题极限是4*10^6*log(2*10^4),2为底，二分，所以4*10^10，128MB差不多存10^8，爆内存
用时间换空间的回收冗余编号机制
*/
void recycle(int x)//垃圾回收，节省内存，因为内存开销太大，容易爆内存，记录用过但是已经删除的节点的编号，新建节点的时候直接从队列或者栈中取出来用就可以。时间换空间
{
    int &l=tree[x][0],&r=tree[x][1];
    if(l) recycle(l);
    if(r) recycle(r);//垃圾回收，一直回收到底
    q.push(x);
    fa[x]=tag[x]=rev[x]=l=r=0;
}

/*
核心操作之三
通过split 找到[k+1,k+tot]，然后把k，k+tot+1移到根和右儿子的位置
然后返回这个右儿子的左儿子，就是要操作的区间
*/
int split(int k,int tot)
{
    int x=find(rt,k),y=find(rt,k+tot+1);
    splay(x,rt);splay(y,tree[x][1]);
    return tree[y][0];
}

void query(int k,int tot)//区间最大子段和
{
    int x=split(k,tot);
    printf("%d
",sum[x]);
}

void modify(int k,int tot,int value)//当前数列第k个开始连续tot个统一修改为value
{
    int x=split(k,tot),y=fa[x];
    val[x]=value;tag[x]=1;sum[x]=sz[x]*value;
    if(value>=0) lx[x]=rx[x]=mx[x]=sum[x];
    else         lx[x]=rx[x]=0,mx[x]=value;//最大的子段和就是一个，因为是负数
    pushup(y);pushup(fa[y]);//每一步的修改操作，父子关系发生变化，记录标记发生变化，所以要及时标记上传
}

void rever(int k,int tot)//当前数列第k个开始的tot个数字翻转
{
    int x=split(k,tot),y=fa[x];
    if(!tag[x]){
        rev[x]^=1;
        swap(tree[x][0],tree[x][1]);
        swap(lx[x],rx[x]);
        pushup(y);pushup(fa[y]);
    }
}

void erase(int k,int tot)//当前数列第k个数字开始连续删除tot个数字
{
    int x=split(k,tot),y=fa[x];
    recycle(x);tree[y][0]=0;
    pushup(y);pushup(fa[y]);
}

void build(int l,int r,int f)
{
    int m=(l+r)>>1,now=id[m],pre=id[f];
    if(l==r){
        mx[now]=sum[now]=a[l];
        tag[now]=rev[now]=0;//这里的清零操作是必要的，因为可能是之前垃圾回收，冗余的
        lx[now]=rx[now]=max(a[l],0);
        sz[now]=1;
    }
    if(l<m) build(l,m-1,m);
    if(r>m) build(m+1,r,m);
    val[now]=a[m];fa[now]=pre;
    pushup(now);
    tree[pre][m>=f]=now;//插入右或者左区间
}

void insert(int k,int tot)//当前数列第k个数字后插入tot个数字
{
    for(int i=1;i<=tot;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=tot;i++){
        if(!q.empty()) id[i]=q.front(),q.pop();
        else id[i]=++cnt;//利用队列里的冗余节点编号
    }
    build(1,tot,0);//将读入的tot个数建成一个平衡树
    int z=id[(1+tot)>>1];//取中点为根
    int x=find(rt,k+1),y=find(rt,k+2);//首先，根据中序遍历，找到要操作的区间的实际编号
    splay(x,rt);splay(y,tree[x][1]);//把k+1(注意我们已经右移了一个单位）和(k+1)+1移到根和右儿子
    fa[z]=y;tree[y][0]=z;//直接把需要插入的这个平衡树挂到右儿子的左儿子上去就好了
    pushup(y);pushup(x);
}

//对于具体在哪里上传标记和下传标记
//可以这么记，只要用了split就要重新上传标记
//只有find中需要下传标记
//但其实，你多传几次是没有关系的，但是少传了就不行了
int main()
{
    scanf("%d%d",&n,&m);
    mx[0]=a[1]=a[n+2]=-inf;//两个虚拟节点，哨兵节点
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i+1]);
    }
    for(int i=1;i<=n+2;i++){//虚拟了两个节点1和n+2，然后把需要操作区间整体右移一个单位
        id[i]=i;
    }
    build(1,n+2,0);
    rt=(n+3)>>1;cnt=n+2;//取最中间的为根，这样就是一个完美的平衡树
    int k,tot,value;char op[10];
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]!='M'||op[2]!='X') scanf("%d%d",&k,&tot);
        if(op[0]=='I') insert(k,tot);
        if(op[0]=='D') erase(k,tot);
        if(op[0]=='M'){
            if(op[2]=='X') printf("%d
",mx[rt]);
            else scanf("%d",&value),modify(k,tot,value);
        }
        if(op[0]=='R') rever(k,tot);
        if(op[0]=='G') query(k,tot);
    }
    return 0;
}