【NOI 2005】维修数列

【题目链接】

点击打开链接

【算法】

本题所运用的也是Splay的区间操作，但是实现较为困难

INSERT操作

将pos splay至根节点，pos+1 splay至根节点的右节点，然后对根节点的右节点的左节点建树即可

DELETE操作

将l-1 splay至根节点， r+1 splay至根节点的右节点，直接“砍断”根节点的右节点的左节点

MAKE_SAME操作

将l-1 splay至根节点，r+1 splay至根节点的右节点，给根节点的右节点的左节点打上标记

REVERSE操作

将l-1 splay至根节点，r+1 splay至根节点的右节点，给根节点的右节点的左节点打上标记

GET_SUM操作

将l-1 splay至根节点，r+1 splay至根节点的右节点，直接输出根节点的右节点的左节点的sum

MAX_SUM操作

此操作的实现类似于树形DP ：

我们不妨给每个节点增加三个域

lmax ：从这个节点所代表的区间的左端点开始向右延伸的最大和

rmax ：从这个节点所代表的区间的右端点开始像左延伸的最大和

max ：该节点所代表区间的最大连续子段和

那么，lmax该如何取值？

令根节点为root，根节点的左儿子为lc，根节点的右儿子为rc

我们可以分情况讨论：

若lmax[root]不包括root，则lmax[root] = lmax[lc]

若lmax[root]包括root，那么：若不向右继续延伸，则lmax[root] = tot[lc] + val[root]，若向右延伸，

则lmax[root] = tot[lc] + val[root] + lmax[rc]

我们只要在这三者中取最大值就可以了

rmax同理

那么，max又该如何取值呢？

我们还是分情况讨论：

令根节点为root，根节点的左儿子为rc，根节点的右儿子为rc

若max[root]不包括root，则max[root] = max{max[lc],max[rc]}

若max[root]包括root，那么 : 若不向右也不向左延伸，则max[root] = val[root],若向左延伸，

则max[root] = val[root] + rmax[lc]

若向右延伸，则：

max[root] = val[root] + lmax[rc]

若两边同时延伸，则：

max[root] = val[root] + rmax[rc] + lmax[lc]

只需在这五者中取最大值即可

关于内存池：

由于本题数据量较大，我们要进行内存回收，内存回收方法如下：

我们建立一个内存池，开始时将所有可用空间都放入内存池，插入一个节点时，我们从内存池弹出一个节点，

分配给这个节点，删除时，我们将要删除的节点放回内存池，如果是删除一棵子树，则将整棵子树放回内存池

这个内存池可以用栈，队列，链表等许多数据结构来维护，笔者选用的是栈，由于维护方法比较简单，笔者不再赘述

【代码】

本题的细节很多，写代码时一定要严谨！

#include<bits/stdc++.h>

using namespace std;

#define MAXN 20000

#define MAXX 500000

const int INF = 2e9;

int i,N,M,tot,pos,val;

int a[MAXX+];

char opt[];

stack<int> stk;

template <typename T> inline void read(T &x) {

        int f = ; x = ;

        char c = getchar();

        for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }

        for (; isdigit(c); c = getchar()) x = x *  + c - '';

        x *= f;

}

template <typename T> inline void write(T x) {

    if (x < ) { putchar('-'); x = -x; }

    if (x > ) write(x/);

    putchar(x%+'');

}

template <typename T> inline void writeln(T x) {

    write(x);

    puts("");

}

struct Splay {

        int root;

        struct Node {

                int fa,son[],size,lmax,rmax,tot,

                        Max,val,lazy;

                bool rev;

        } Tree[MAXX+];

        inline bool get(int x) {

                return Tree[Tree[x].fa].son[] == x;

        }

        inline void build(int index,int l,int r) {

                int id,mid;

                mid = (l + r) >> ;

                Tree[index].lazy = INF;

                Tree[index].rev = ;

                Tree[index].val = a[mid];

                if (l == r) {

                        Tree[index].size = ;

                        Tree[index].lmax = Tree[index].rmax = Tree[index].Max = Tree[index].tot = a[mid];

                        return;

                }

                if (l < mid) {

                        id = stk.top();

                        stk.pop();

                        Tree[index].son[] = id;

                        Tree[id].fa = index;

                        build(id,l,mid-);

                }

                if (mid < r) {

                        id = stk.top();

                        stk.pop();

                        Tree[index].son[] = id;

                        Tree[id].fa = index;

                        build(id,mid+,r);

                }

                update(index);

        }

        inline void update(int index) {

                if (!index) return;

                Tree[index].tot = Tree[Tree[index].son[]].tot + Tree[Tree[index].son[]].tot + Tree[index].val;

                Tree[index].size = Tree[Tree[index].son[]].size + Tree[Tree[index].son[]].size + ;

                Tree[index].lmax = max(Tree[Tree[index].son[]].lmax,Tree[Tree[index].son[]].tot+max(Tree[Tree[index].son[]].lmax,)+Tree[index].val);

                Tree[index].rmax = max(Tree[Tree[index].son[]].rmax,Tree[Tree[index].son[]].tot+max(Tree[Tree[index].son[]].rmax,)+Tree[index].val);

                Tree[index].Max = max(Tree[Tree[index].son[]].Max,max(Tree[Tree[index].son[]].Max,Tree[index].val+max(Tree[Tree[index].son[]].rmax,)+max(Tree[Tree[index].son[]].lmax,)));

        }

        inline void pushdown(int index) {

                int tmp;

                if (Tree[index].lazy != INF) {

                        tmp = Tree[index].lazy;

                        Tree[index].lazy = INF;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].tot = Tree[Tree[index].son[]].size * tmp;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].tot = Tree[Tree[index].son[]].size * tmp;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].val = tmp;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].val = tmp;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].lmax = Tree[Tree[index].son[]].rmax = Tree[Tree[index].son[]].Max = max(tmp,Tree[Tree[index].son[]].size*tmp);

                        if (Tree[index].son[]) Tree[Tree[index].son[]].lmax = Tree[Tree[index].son[]].rmax = Tree[Tree[index].son[]].Max = max(tmp,Tree[Tree[index].son[]].size*tmp);

                        if (Tree[index].son[]) Tree[Tree[index].son[]].lazy = tmp;

                        if (Tree[index].son[]) Tree[Tree[index].son[]].lazy = tmp;

                }

                if (Tree[index].rev) {

                        swap(Tree[index].son[],Tree[index].son[]);

                        swap(Tree[Tree[index].son[]].lmax,Tree[Tree[index].son[]].rmax);

                        swap(Tree[Tree[index].son[]].lmax,Tree[Tree[index].son[]].rmax);

                        Tree[Tree[index].son[]].rev ^= ;

                        Tree[Tree[index].son[]].rev ^= ;

                        Tree[index].rev = ;

                }

        }

        inline int query_pos(int x) {

                int index = root;

                while (true) {

                        pushdown(index);

                        if (x > Tree[Tree[index].son[]].size) {

                                x -= Tree[Tree[index].son[]].size;

                                if (x == ) return index;

                                --x;

                                index = Tree[index].son[];

                        } else index = Tree[index].son[];

                }

        }

        inline void clear(int index) {

                Tree[Tree[index].fa].son[get(index)] = ;

                Tree[index].fa = ;

                stk.push(index);

                if (Tree[index].son[]) clear(Tree[index].son[]);

                if (Tree[index].son[]) clear(Tree[index].son[]);

        }

        inline void Insert(int index) {

                int id;

                int x = query_pos(index),

                        y = query_pos(index+);

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

                id = stk.top();

                stk.pop();

                build(id,,tot);

                Tree[Tree[root].son[]].son[] = id;

                Tree[id].fa = Tree[root].son[];

                update(Tree[root].son[]);

                update(root);

        }

        inline void rotate(int x) {

                int f = Tree[x].fa,g = Tree[f].fa,

                tmpx = get(x),tmpf = get(f);

                pushdown(f); pushdown(x);

                if (!f) return;

                Tree[f].son[tmpx] = Tree[x].son[tmpx^];

                if (Tree[x].son[tmpx^]) Tree[Tree[x].son[tmpx^]].fa = f;

                Tree[x].son[tmpx^] = f;

                Tree[f].fa = x;

                Tree[x].fa = g;

                if (g) Tree[g].son[tmpf] = x;

                update(f);

                update(x);

        }

        inline void splay(int x,int pos) {

                int f;

                for (f = Tree[x].fa; (f = Tree[x].fa) != pos; rotate(x)) {

                        if (Tree[f].fa != pos)

                                rotate(get(f) == get(x) ? (f) : (x));

                }

                if (!pos) root = x;

        }

        inline void modify(int l,int r,int v) {

                int x = query_pos(l-),

                        y = query_pos(r+);

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

                int tmp = Tree[Tree[root].son[]].son[];

                Tree[tmp].val = Tree[tmp].lazy = v;

                Tree[tmp].tot = v * Tree[tmp].size;

                Tree[tmp].lmax = Tree[tmp].rmax = Tree[tmp].Max = max(Tree[tmp].size*v,v);

                update(Tree[root].son[]);

                update(root);

        }

        inline void reverse(int l,int r) {

                int x = query_pos(l-),

                        y = query_pos(r+);

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

                Tree[Tree[Tree[root].son[]].son[]].rev ^= ;

                swap(Tree[Tree[Tree[root].son[]].son[]].lmax,Tree[Tree[Tree[root].son[]].son[]].rmax);

        }

        inline void erase(int l,int r) {

                int x = query_pos(l-),

                        y = query_pos(r+);

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

                clear(Tree[Tree[root].son[]].son[]);

                Tree[Tree[root].son[]].son[] = ;

                update(Tree[root].son[]);

                update(root);

        }

        int get_sum(int l,int r) {

                int x = query_pos(l-),

                        y = query_pos(r+);

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

                return Tree[Tree[Tree[root].son[]].son[]].tot;

        }

        int max_sum(int l,int r) {

                int x = query_pos(l-),

                        y = query_pos(r+);

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

                return Tree[Tree[Tree[root].son[]].son[]].Max;

        }

} T;

int main() {

        read(N); read(M);

        for (i = ; i <= MAXX; i++) stk.push(i);

        a[] = a[N+] = -INF;

        for (i = ; i <= N + ; i++) read(a[i]);

        T.Tree[].lmax = T.Tree[].rmax = T.Tree[].Max = -INF;

        T.root = ;

        T.build(,,N+);

        while (M--) {

                scanf("%s",&opt);

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

                        read(pos); read(tot);

                        for (i = ; i <= tot; i++) read(a[i]);

                        T.Insert(pos+);

                        N += tot;

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

                        read(pos); read(tot);

                        T.erase(pos+,pos+tot);

                        N -= tot;

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

                        read(pos); read(tot); read(val);

                        T.modify(pos+,pos+tot,val);

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

                        read(pos); read(tot);

                        T.reverse(pos+,pos+tot);

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

                        read(pos); read(tot);

                        writeln(T.get_sum(pos+,pos+tot));

                } else if (opt[] == 'M' && opt[] == 'X') {

                        writeln(T.max_sum(,N+));

                }

        }

        return ;

}

巴特西

【NOI 2005】维修数列

最新文章

热门文章

巴特西

【NOI 2005】 维修数列

最新文章

热门文章

【NOI 2005】维修数列