维修数列-平衡树

题目链接

  题意就是一个简单的平衡树的板子，但是在实现上有很多细节,蒟蒻的我竟然debug了3天，只能说自己的板子不硬，更新下板子
 因为细节挺多的(至少我觉得是，所以就直接以注释的形式写在代码里了)但是要注意，这里说的子列是连续的子列。
 因为看网上的题解说的好像在bzoj上一直开新点会内存超限，为了防止也出现这个情况，我特意学了一手节点回收分配(虽然最后也没啥用好像)

超长代码(捂脸)

#include <bits/stdc++.h>
#define ss system("pause");

using namespace std;

const int maxn = 500000;
const int INF = 1e9;

/********************
splay树
********************/

struct  node
{
    int f,val,size,ch[2],cnt;
    int sum,lmax,rmax,maxsum;
    bool rev,tag;
    node() {}
    node(int v){
        f = ch[0] = ch[1] = rev = tag = 0;
        size = cnt = 1;
        val = sum = lmax = rmax = maxsum = v;
    }
}tree[maxn];

int root,sz,top;
int org[maxn],sta[maxn];

inline void splay(int x,int goal);
int findkth(int x);

//节点分配回收机制
inline int new_node()
{
    return top?sta[top--]:++sz;
}

inline void update(int x)
{
    //对0节点进行初始赋值的原因就在于防止0节点影响对于有负值节点的更新
    //会造成负数值的更新出现问题
    int lc = tree[x].ch[0],rc = tree[x].ch[1];
    tree[x].size = tree[lc].size + tree[rc].size + 1;
    tree[x].sum = tree[lc].sum + tree[rc].sum + tree[x].val;
    tree[x].maxsum = max(max(tree[lc].maxsum,tree[rc].maxsum),max(0,tree[lc].rmax) + tree[x].val + max(0,tree[rc].lmax));
    tree[x].lmax = max(tree[lc].lmax,max(0,tree[rc].lmax) + tree[x].val + tree[lc].sum);
    tree[x].rmax = max(tree[rc].rmax,max(0,tree[lc].rmax) + tree[x].val + tree[rc].sum);
}

void Replace(int x,int d)
{
    if(!x) return ;
    tree[x].val = d;
    tree[x].sum = d * tree[x].size;
    tree[x].maxsum = tree[x].lmax = tree[x].rmax = max(d,d * tree[x].size);
    tree[x].rev = 0,tree[x].tag = 1;
}

void Mak(int pos,int tot,int d)//把指定区间全部转化成指定值
{
    int l = pos - 1,r = pos + tot;
    l = findkth(l),r = findkth(r);
    splay(l,0),splay(r,l);
    int u = tree[root].ch[1];
    Replace(tree[u].ch[0],d);
    update(u),update(root);
}

inline void rev(int x)
{
    if(tree[x].tag) return ;
    tree[x].rev ^= 1;
    swap(tree[x].ch[0],tree[x].ch[1]);
    swap(tree[x].lmax,tree[x].rmax);//左右的最大值也会跟着反转
}

inline void pushdown(int x)
{
    if(tree[x].rev){
        if(tree[x].ch[0]) rev(tree[x].ch[0]);
        if(tree[x].ch[1]) rev(tree[x].ch[1]);
        tree[x].rev = 0;
    }
    if(tree[x].tag){
        if(tree[x].ch[0]) Replace(tree[x].ch[0],tree[x].val);
        if(tree[x].ch[1]) Replace(tree[x].ch[1],tree[x].val);
        tree[x].tag = 0;
    }
}

inline void rotate(int x)
{
    int fa = tree[x].f,gfa = tree[fa].f;
    pushdown(x),pushdown(fa), pushdown(gfa);
    //判断x是父节点的哪个儿子，0为左，1为右
    int k = (tree[fa].ch[1] == x);
    //把x的父节点在gfa的位置用x取代
    tree[gfa].ch[tree[gfa].ch[1] == fa] = x;
    tree[x].f = gfa;//x的父亲节点变成了gfa
    tree[fa].ch[k] = tree[x].ch[k^1];
    tree[tree[x].ch[k^1]].f = fa;
    tree[x].ch[k^1] = fa;
    tree[fa].f = x;
    update(fa),update(x);
}

inline void splay(int x,int goal)
{
    //pushdown(x);
    while(tree[x].f != goal){
        int fa = tree[x].f , gfa = tree[fa].f;
        if(gfa != goal){
            ((tree[gfa].ch[0] == fa) ^ (tree[fa].ch[0] == x)) ? rotate(x) : rotate(fa);
        }
        rotate(x);
    }
    if(goal == 0) root = x;
}

void build_tree(int &rt,int l, int r, int fa)
{
    int mid = (l + r) >> 1;
    rt = new_node();
    tree[rt] = node(org[mid]);
    tree[rt].f = fa;
    if(l == r) return ;
    if(l < mid) build_tree(tree[rt].ch[0],l, mid - 1,rt);
    if(r > mid) build_tree(tree[rt].ch[1],mid + 1,r, rt);
    update(rt);
}

int findkth(int x)
{
    if(tree[root].size < x) return -1;
    int u = root;
    while(1){
        pushdown(u);
        if(x <= tree[tree[u].ch[0]].size){
            u = tree[u].ch[0];
        }
        else if(x <= tree[tree[u].ch[0]].size + tree[u].cnt){
            return u;
        }
        else{
            x -= (tree[tree[u].ch[0]].size + tree[u].cnt);
            u = tree[u].ch[1];
        }
    }
}

 void Reverse(int x,int tot)
 {
     int l = x - 1,r = x + tot;
     l = findkth(l) , r = findkth(r);
     splay(l,0),splay(r,l);
     int u = tree[root].ch[1];
     int pos = tree[u].ch[0];
    if(tree[pos].tag) return ;//如果这个区间已经被标记整体修改了，就没有必要反转了
    rev(pos);
    //这里反转不能像之前一样打标记就可以了
    //因为反转完这个序列的最大左右值肯定会变化
    //所以要直接反转完并进行值的更新,这个标记是指的子节点
    update(u),update(root);
 }

void erase(int x)
{
    if(!x) return ;
    sta[++top] = x;
    erase(tree[x].ch[0]),erase(tree[x].ch[1]);
}

void cut(int a,int tot)
{
    int l = a - 1,r = a + tot;
    l = findkth(l) , r = findkth(r);
    splay(l,0),splay(r,l);
    int u = tree[root].ch[1];
    erase(tree[u].ch[0]),tree[u].ch[0] = 0;
    update(u),update(root);
}

void add(int pos,int tot)
{
    for(int i = 1; i <= tot; i++){
        scanf("%d",org + i);
    }
    //将区间[a,b]后接到c后面
    int l = pos,  r = pos + 1;
    l = findkth(l) , r = findkth(r);
    splay(l,0) , splay(r, l);
    int u = tree[root].ch[1];
    build_tree(tree[u].ch[0],1,tot,u);
    update(u),update(root);
}

//获取区间和
int Get_Sum(int pos,int tot)
{
    int l = pos - 1,r = pos + tot;
    l = findkth(l) , r = findkth(r);
    splay(l,0), splay(r,l);
    int u = tree[root].ch[1];
    return tree[tree[u].ch[0]].sum;
}

void inorder(int rt)
{
    if(!rt) return ;
    pushdown(rt);
    if(tree[rt].ch[0]) inorder(tree[rt].ch[0]);
    cout<<tree[rt].val<<' ';
    if(tree[rt].ch[1]) inorder(tree[rt].ch[1]);
}

int main()
{
    int n,q;
    string s;
    scanf("%d%d",&n,&q);
    for(int i = 1; i <= n; i++) scanf("%d",org + i + 1);
    org[1] = org[n + 2] = -INF;
    //由于不存在的节点标志为0，所以为了防止update时把0节点也错误计算进去，要对0节点进行赋值
    //-INF是为了防止更新区间最大值的时候，把一些节点的负数值判定为0，造成部分的最大值的和会偏大
    tree[0] = node(-INF),tree[0].size = tree[0].sum = 0;
    build_tree(root,1,n + 2,0);        
    while(q--){
        cin>>s;
        if(s == "MAX-SUM") printf("%d\n",tree[root].maxsum);
        else {
            int pos,tot;
            scanf("%d%d",&pos,&tot);
            if(s == "GET-SUM"){
                int ans = Get_Sum(pos + 1,tot);
                printf("%d\n",ans);
            }
            if(s == "INSERT") add(pos + 1,tot);
            if(s == "MAKE-SAME"){
                int d;
                scanf("%d",&d);
                Mak(pos + 1,tot,d);
            }
            if(s == "DELETE") cut(pos + 1,tot);
            if(s == "REVERSE") Reverse(pos + 1,tot);
        }
        //inorder(root);
        //cout<<endl;
    }
    //ss;
    return 0;
}