WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Splay模板
Splay模板
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

namespace Splay{ // 在1位置与n+2个位置插入空节点,操作时序号不变
    const int MAXN=2e5+50;
    #define ls(x) tree[x].ch[0]
    #define rs(x) tree[x].ch[1]
    #define fa(x) tree[x].fa
    struct BTree{
        int ch[2], fa, siz, rev; // 子节点,父节点,子树大小,结点数量,翻转标记
        int val, min, add; // 维护区间最小值
    }tree[MAXN];
    queue<int> que; int numt; // 结点回收与分配
    int root; // 根节点
    int num[MAXN]; // 新建元素数组

    inline int newNode(int f){
        int x; if (!que.empty()) x=que.front(), que.pop(); else x=++numt;
        ls(x)=rs(x)=tree[x].siz=tree[x].rev=0; fa(x)=f;
        return x;
    }
    inline void delNode(int x){ que.push(x); } // 删除结点
    inline void delSplay(int x){ if (!x) return; delSplay(ls(x)), delSplay(rs(x)); delNode(x); } // 删除子树

    void rev(int x){ // 翻转结点信息
        if (!x) return; 
        swap(ls(x), rs(x)); tree[x].rev^=1; 
        // ?维护翻转时的信息变化
    } 
    void update(int x){ // 更新结点信息
        tree[x].siz=tree[ls(x)].siz+tree[rs(x)].siz+1;
        // ?维护其他信息
        tree[x].min=tree[x].val;
        if (ls(x) && tree[ls(x)].min<tree[x].min) tree[x].min=tree[ls(x)].min; 
        if (rs(x) && tree[rs(x)].min<tree[x].min) tree[x].min=tree[rs(x)].min;
    }
    void clean(int x){ // 下推结点标记
        if (tree[x].rev) rev(ls(x)), rev(rs(x)), tree[x].rev=0;
        // ?维护标记
        if (tree[x].add){
            int tag=tree[x].add; tree[x].add=0;
            if (ls(x)) tree[ls(x)].val+=tag, tree[ls(x)].min+=tag, tree[ls(x)].add+=tag;
            if (rs(x)) tree[rs(x)].val+=tag, tree[rs(x)].min+=tag, tree[rs(x)].add+=tag;
        }
    }
    void init(){ // 初始化Splay
        ls(0)=rs(0)=fa(0)=tree[0].siz=tree[0].rev=0; 
        // 这里初始化零号结点其他信息
        while(!que.empty()) que.pop(); numt=0; root=newNode(0);  update(root);
    }

    /** 建树三连
     *  Splay::init(); // 新建Splay
     *  for (int i=2; i<=n+1; i++) scanf("%d", &Splay::num[i]); // 实际元素从2~n+1,操作标号不改变
     *  Splay::root=Splay::build(1, n+2, 0); 
     */

    inline int ident(int x){ return rs(fa(x))==x; } // 判断结点是其父亲的那个孩子
    int build(int l, int r, int f){ // 建立Splay
        if (l>r) return 0;
        int m=(l+r)/2, x=newNode(f);
        tree[x].min=tree[x].val=num[m], tree[x].add=0;
        ls(x)=build(l, m-1, x);
        rs(x)=build(m+1, r, x);
        update(x);
        return x;
    }
    void rotate(int x, int &k){ // 将结点x旋转到结点k位置
        int y=fa(x), z=fa(y);
        int l=ident(x), r=l^1;
        if (y==k) k=x; else tree[z].ch[ident(y)]=x;
        fa(tree[x].ch[r])=y; fa(y)=x; fa(x)=z;
        tree[y].ch[l]=tree[x].ch[r]; tree[x].ch[r]=y;
        update(y); update(x);
    }

    void splay(int x, int &k){ // 将结点xSplay到结点k位置
        while(x!=k){
            int y=fa(x), z=fa(y);
            if(y!=k){ if (ls(y)==x ^ ls(z)==y) rotate(x, k); else rotate(y, k); }
            rotate(x, k);
        }
    }

    int find(int x, int k){ // 查找第k个元素编号
        clean(x);
        if (tree[ls(x)].siz+1==k) return x;
        if (k<=tree[ls(x)].siz) return find(ls(x), k); 
        return find(rs(x), k-tree[ls(x)].siz-1);
    }

    int split(int k, int tot){ // 提取从第k个元素开始的连续tot个元素(提取到左孩子)
        int x=find(root,k), y=find(root,k+tot+1);
        splay(x, root); splay(y, rs(x));
        return ls(y);
    }

    void erase(int k, int tot){ // 删除从第k个元素开始的连续tot个元素
        int x=split(k, tot), y=fa(x);
        delSplay(x); ls(y)=0;
        update(y); update(fa(y));
    }

    int cut(int k, int tot){ // 剪切从第k个元素开始的连续tot个元素
        int x=split(k, tot), y=fa(x);
        fa(x)=0; ls(y)=0;
        update(y); update(fa(y));
        return x;
    }

    void join(int k, int z){ // 在第k个元素之后插入z为根的Splay(0为序列开头)
        int x=find(root, k+1), y=find(root, k+2); // 找到k+1与k+2个元素
        splay(x, root); splay(y, rs(x)); // 将x转到根,y转到x的右孩子,将y的左孩子空出
        ls(y)=z; fa(z)=y; 
        update(y); update(x);
    }

    void reverse(int k, int tot){ // 反转从第k个元素开始的连续tot个元素(其他修改同理)
        int x=split(k, tot), y=fa(x);
        rev(x); // 修改过程
        update(y); update(fa(y));
    }

    void shift(int k, int tot, int D){ // [K, K+tot-1] 区间右移D
        D%=tot; if (D==0) return; 
        join(k-1, cut(k+tot-D, D));
    }

    void add(int k, int tot, int D){ // [K, K+tot-1] 区间加D
        int x=split(k, tot), y=fa(x);
        tree[x].min+=D; tree[x].val+=D; tree[x].add+=D;
        update(y); update(fa(y));
    }
}


int main(){
    int n, Q; scanf("%d", &n);
    scanf("%d", &Q);
    for (int r=1; r<=Q; r++){
        char op[10]; scanf("%s", op); // printf("%s\n", op); fflush(stdout);
        if (op[0]=='A'){ // [x, y]区间+D
            int x, y, D; scanf("%d%d%d", &x, &y, &D);
            Splay::add(x, y-x+1, D);
        }
        if (op[0]=='R' && op[3]=='E'){ // [x, y]区间翻转
            int x, y; scanf("%d%d", &x, &y);
            Splay::reverse(x, y-x+1);
        }
        if (op[0]=='R' && op[3]=='O'){ // [x, y]区间右移
            int x, y, D; scanf("%d%d%d", &x, &y, &D);
            Splay::shift(x, y-x+1, D);
        }
        if (op[0]=='I'){ // x元素后插入D元素
            int x; scanf("%d%d", &x, &Splay::num[1]);
            int y= Splay::build(1, 1, 0);
            Splay::join(x, y);
        }
        if (op[0]=='D'){ // 删除元素x
            int x; scanf("%d", &x);
            Splay::erase(x, 1);
        }
        if (op[0]=='M'){ // [x, y]区间求最小值
            int x, y; scanf("%d%d", &x, &y);
            x=Splay::split(x, y-x+1);
            printf("%d\n", Splay::tree[x].min);
        }
    }
    return 0;
}

题目编号:POJ 2580

赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Splay模板
#include <cstdio> #include <cstring> #include <queue> using namespace std; namespace Splay{ // 在1位置与n+2个位置插入空节点,操作时序号不变 const int M…
扫描二维码继续阅读
2018-10-17
<--! http2https -->