2013-team4/code/splay

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
const int INF = 2147480000, N = 200100;

struct Node{
    int size;
    Node *f, *ch[2];
    int v, rev, add, mx;        // 根据题意具体修改

    int lr();           // 返回自己是左(0) / 右(1)儿子
    void rotate();          // 向上旋转
    Node* splay(Node *goal);    // splay 到某结点下, 不传参数则到根
    Node* set(int d, Node *c);  // 设置左(0) / 右(1)儿子
    Node* pushDown();       // 标记下传
    Node* update();         // 用儿子的信息更新自己

    void exeAdd(int a){
        add += a;
        v += a;
        mx += a;
    }
}pool[N], *null;            // 内存池, null 替代 NULL

int Node::lr(){
    return int(f->ch[1] == this);
}
Node* Node::set(int d, Node *c){
    ch[d] = c;
    return c->f = this;
}
void Node::rotate(){
    Node *x = f;
    int d = lr() ^ 1;
    x->set(d ^ 1, ch[d]);
    x->f->set(x->lr(), this);
    set(d, x);
    x->update();
    update();

}
Node* Node::splay(Node *goal = null){
    for(pushDown(); f != goal; rotate()){
        f->f->pushDown();
        f->pushDown();
        pushDown();
        if(f->f != goal){
            if(f->lr() == lr()) f->rotate();
            else rotate();
        }
    }
    return this;
}
// 根据题意具体修改
Node* Node::update(){
    if(this != null){
        size = ch[0]->size + ch[1]->size + 1;
        mx = max(v, max(ch[0]->mx, ch[1]->mx));
    }
    return this;
}
// 根据题意具体修改
Node* Node::pushDown(){
    if(this != null){
        if(rev){
            swap(ch[0], ch[1]);
            for(int i = 0; i < 2; i++) if(ch[i] != null)
                ch[i]->rev ^= 1;
            rev = 0;
        }
        if(add != 0){
            for(int i = 0; i < 2; i++) if(ch[i] != null)
                ch[i]->exeAdd(add);
            add = 0;
        }
    }
    return this;
}

int Cnt;
// 根据题意具体修改
Node* newNode(int val){
    Node *p = &pool[Cnt++];
    p->f = p->ch[0] = p->ch[1] = null;
    p->size = 1;
    p->rev = 0;
    p->v = val;
    p->mx = val;
    p->add = 0;
    return p;
}
// !!! 必须先调用 init
void init(){
    Cnt = 0;
    null = newNode(-INF);
    null->size = 0;
}
// 用 a[l, r] 建立平衡的树, 返回树根
Node* build(int l, int r, int a[]){
    if(l > r) return null;
    int mid = (l + r) / 2;
    Node *p = newNode(a[mid]);
    if(l < r){
        p->set(0, build(l, mid - 1, a));
        p->set(1, build(mid + 1, r, a));
        p->update();
    }
    return p;
}
// 返回树中第 k 个结点, 下标从 1 开始
Node* select(Node *root, int k){
    for(Node *p = root; true; ){
        p->pushDown();
        int lsize = p->ch[0]->size;
        if(k <= lsize) p = p->ch[0];
        else{
            k -= lsize + 1;
            if(k == 0) return p;
            p = p->ch[1];
        }
    }
}
// 返回 [l, r] 的子树, 会修改根
Node* range(Node *&root, int l, int r){
    if(l == 1 && r == root->size) return root;
    if(l == 1){
        root = select(root, r + 1)->splay();
        return root->ch[0];
    }
    root = select(root, l - 1)->splay();
    if(r == root->size) return root->ch[1];
    return select(root, r + 1)->splay(root)->ch[0];
}
// 翻转 [l, r] 区间, 返回树根
Node* reverse(Node *root, int l, int r){
    range(root, l, r)->rev ^= 1;
    return root;
}
// 合并两棵树, 返回树根 
Node* merge(Node *p, Node *q){
    p->f = q->f = null;
    if(p == null) return q;
    if(q == null) return p;
    q = select(q, 1);
    return q->splay()->set(0, p)->update();
}
// 删除以 p 为根的子树, 返回树根
Node* erase(Node *p){
    if(p->f == null) return null;
    Node *q = p->f->pushDown();
    return q->set(p->lr(), null)->update()->splay();
}
// 删除第 k 个元素, 返回树根
Node* erase(Node *root, int k){
    Node *p = select(root, k)->splay();
    return merge(p->ch[0], p->ch[1]);
}
// 在 p 之前插入 q, 返回树根 
Node* insert(Node *p, Node *q){
    p->splay();
    if(p->ch[0] == null){
        p->set(0, q);
    }
    else{
        select(p, p->ch[0]->size)->splay(p)->set(1, q)->update();
    }
    p->update();
    return p;
}
// 在第 k 个元素前插入 p, 返回树根
Node* insert(Node *root, int k, Node *p){
    if(root == null) return p;
    if(k > root->size){
        return select(root, root->size)->splay()->set(1, p)->update();
    }
    else{
        return insert(select(root, k), p);
    }
}
// 给 [l, r] 区间加上一个数, 返回树根
Node* addVal(Node *root, int l, int r, int val){
    Node *p = range(root, l, r);
    p->exeAdd(val);
    return p->splay();
}
// 将 [l, r] 区间循环右移 t 位
Node* revolve(Node *root, int l, int r, int t){
    if(t == 0) return root;
    Node *p = range(root, r - t + 1, r);
    root = erase(p); p->f = null;
    return insert(root, l, p);
}
// 区间查询最大值
Node* queryMax(Node *root, int l, int r){
    Node *p = range(root, l, r);
    cout << p->mx << endl;
    return root;
}
}}}

{{{
/*
Splay模板 by zimpha
这道题目是POJ 3580 SuperMemo
实现了rot, splay, select, get_seq等基本功能
实现了区间反转，整段区间操作(+,覆盖之类的)，插入一个数，删除一个数
要获取区间[l, r]直接调用get_seq(l-1, r+1)即可。
每次使用前必须先调用init()函数
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=100000+10;
const int inf=~0U>>2;

struct node {
    node *ch[2], *p;
    int size, add, val, Min, rev;
    node () {size=0; val=inf;}
    bool d() {return this==p->ch[1];}
    void setc(node *c, int d) {ch[d]=c; c->p=this;}
    void markAdd(int _add) {
        add+=_add, val+=_add, Min+=_add;
    }
    void markRev() {
        rev^=1; swap(ch[0], ch[1]);
    }
    void update() {
        size=ch[0]->size+ch[1]->size+1;
        Min=min(val, min(ch[0]->Min, ch[1]->Min));
    }
}*null, *root;
node mem[MAXN*2], *stk[MAXN*2];
int A[MAXN], N, M, top;

inline void pushdown(node *t) {
    if (t==null) return;
    if (t->add) {
        if (t->ch[0]!=null) t->ch[0]->markAdd(t->add);
        if (t->ch[1]!=null) t->ch[1]->markAdd(t->add);
    }
    if (t->rev) {
        if (t->ch[0]!=null) t->ch[0]->markRev();
        if (t->ch[1]!=null) t->ch[1]->markRev();
    }
    t->add=t->rev=0;
}

inline node *new_node(int v) {
    node *ret=stk[--top];
    ret->val=v; ret->size=1; ret->Min=v; ret->add=0;
    ret->ch[0]=ret->ch[1]=ret->p=null;
    return ret;
}

inline void recycle(node *x) {
    stk[top++]=x;
}

inline node* rot(node *t) {
    node *p=t->p;
    pushdown(p); pushdown(t);
    int d=t->d();
    p->p->setc(t, p->d());
    p->setc(t->ch[!d], d);
    t->setc(p, !d);
    p->update();
    if (p==root) root=t;
    return t;
}

inline void splay(node *t, node *f) {
    for (pushdown(t); t->p!=f;) {
        if (t->p->p==f) rot(t);
        else t->d()==t->p->d() ? (rot(t->p), rot(t)) : (rot(t), rot(t));
    }
    t->update();
}

inline node *select(int k) {
    for (node *t=root;;) {
        pushdown(t);
        int c=t->ch[0]->size;
        if (k==c) return t;
        if (k>c) k-=c+1, t=t->ch[1];
        else t=t->ch[0];
    }
    return null;
}

inline node *get_seq(int l, int r) {
    node *L=select(l); splay(L, null);
    node *R=select(r); splay(R, root);
    return root->ch[1]->ch[0];
}

node *build_tree(int *l, int *r) {
    if (l>=r) return null;
    if (l+1==r) return new_node(*l);
    int *m=l+(r-l)/2;
    node *t=new_node(*m);
    t->setc(build_tree(l, m), 0);
    t->setc(build_tree(m+1, r), 1);
    t->update(); return t;
}

void init() {
    for (int i=0; i<2*MAXN; i++) stk[i]=mem+i; top=MAXN*2;
    null=new_node(inf); null->size=0; null->Min=inf;
    null->ch[0]=null->ch[1]=null->p=null;
    A[0]=A[N+1]=inf;
    root=build_tree(A, A+N+2);
}

void ADD() {
    int x, y, D; scanf("%d%d%d", &x, &y, &D);
    node *t=get_seq(x-1, y+1);
    t->markAdd(D); splay(t, null);
}

void REVERSE() {
    int x, y; scanf("%d%d", &x, &y);
    node *t=get_seq(x-1, y+1);
    t->markRev(); splay(t, null);
}

void REVOLVE() {
    int x, y, T; scanf("%d%d%d", &x, &y, &T);
    int n=y-x+1; T%=n; if (T==0) return;
    node *t=get_seq(x-1, x+n-T);
    t->p->setc(null, 0); splay(root->ch[1], null);
    get_seq(x+T-1, x+T);
    root->ch[1]->setc(t, 0); splay(t, null);
}

void INSERT() {
    int x, P; scanf("%d%d", &x, &P); A[0]=P;
    node *t=build_tree(A, A+1);
    get_seq(x, x+1);
    root->ch[1]->setc(t, 0);
    splay(t, null);
}

void DELETE() {
    int x; scanf("%d", &x);
    node *t=get_seq(x-1, x+1);
    t->p->setc(null, 0); splay(root->ch[1], null);
    recycle(t);
}

void MIN() {
    int x, y; scanf("%d%d", &x, &y);
    node *t=get_seq(x-1, y+1);
    printf("%d\n", t->Min);
}

int main() {
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%d", A+i);
    init();
    scanf("%d", &M);
    while (M--) {
        char CMD[20];
        scanf("%s", CMD);
        if (CMD[0]=='A') ADD();
        else if (CMD[0]=='I') INSERT();
        else if (CMD[0]=='D') DELETE();
        else if (CMD[0]=='M') MIN();
        else if (CMD[3]=='E') REVERSE();
        else if (CMD[3]=='O') REVOLVE();
    }
    return 0;
}
}}}

const int INF = 2147480000, N = 200100;
struct Node{
    int size;
    Node *f, *ch[2];
    int v, rev, add, mx;        // 根据题意具体修改
    int lr();           // 返回自己是左(0) / 右(1)儿子
    void rotate();          // 向上旋转
    Node* splay(Node *goal);    // splay 到某结点下, 不传参数则到根
    Node* set(int d, Node *c);  // 设置左(0) / 右(1)儿子
    Node* pushDown();       // 标记下传
    Node* update();         // 用儿子的信息更新自己
    void exeAdd(int a){
        add += a;
        v += a;
        mx += a;
    }
}pool[N], *null;            // 内存池, null 替代 NULL
int Node::lr(){
    return int(f->ch[1] == this);
}
Node* Node::set(int d, Node *c){
    ch[d] = c;
    return c->f = this;
}
void Node::rotate(){
    Node *x = f;
    int d = lr() ^ 1;
    x->set(d ^ 1, ch[d]);
    x->f->set(x->lr(), this);
    set(d, x);
    x->update();
    update();
}
Node* Node::splay(Node *goal = null){
    for(pushDown(); f != goal; rotate()){
        f->f->pushDown();
        f->pushDown();
        pushDown();
        if(f->f != goal){
            if(f->lr() == lr()) f->rotate();
            else rotate();
        }
    }
    return this;
}
// 根据题意具体修改
Node* Node::update(){
    if(this != null){
        size = ch[0]->size + ch[1]->size + 1;
        mx = max(v, max(ch[0]->mx, ch[1]->mx));
    }
    return this;
}
// 根据题意具体修改
Node* Node::pushDown(){
    if(this != null){
        if(rev){
            swap(ch[0], ch[1]);
            for(int i = 0; i < 2; i++) if(ch[i] != null)
                ch[i]->rev ^= 1;
            rev = 0;
        }
        if(add != 0){
            for(int i = 0; i < 2; i++) if(ch[i] != null)
                ch[i]->exeAdd(add);
            add = 0;
        }
    }
    return this;
}
int Cnt;
// 根据题意具体修改
Node* newNode(int val){
    Node *p = &pool[Cnt++];
    p->f = p->ch[0] = p->ch[1] = null;
    p->size = 1;
    p->rev = 0;
    p->v = val;
    p->mx = val;
    p->add = 0;
    return p;
}
// !!! 必须先调用 init
void init(){
    Cnt = 0;
    null = newNode(-INF);
    null->size = 0;
}
// 用 a[l, r] 建立平衡的树, 返回树根
Node* build(int l, int r, int a[]){
    if(l > r) return null;
    int mid = (l + r) / 2;
    Node *p = newNode(a[mid]);
    if(l < r){
        p->set(0, build(l, mid - 1, a));
        p->set(1, build(mid + 1, r, a));
        p->update();
    }
    return p;
}
// 返回树中第 k 个结点, 下标从 1 开始
Node* select(Node *root, int k){
    for(Node *p = root; true; ){
        p->pushDown();
        int lsize = p->ch[0]->size;
        if(k <= lsize) p = p->ch[0];
        else{
            k -= lsize + 1;
            if(k == 0) return p;
            p = p->ch[1];
        }
    }
}
// 返回 [l, r] 的子树, 会修改根
Node* range(Node *&root, int l, int r){
    if(l == 1 && r == root->size) return root;
    if(l == 1){
        root = select(root, r + 1)->splay();
        return root->ch[0];
    }
    root = select(root, l - 1)->splay();
    if(r == root->size) return root->ch[1];
    return select(root, r + 1)->splay(root)->ch[0];
}
// 翻转 [l, r] 区间, 返回树根
Node* reverse(Node *root, int l, int r){
    range(root, l, r)->rev ^= 1;
    return root;
}
// 合并两棵树, 返回树根 
Node* merge(Node *p, Node *q){
    p->f = q->f = null;
    if(p == null) return q;
    if(q == null) return p;
    q = select(q, 1);
    return q->splay()->set(0, p)->update();
}
// 删除以 p 为根的子树, 返回树根
Node* erase(Node *p){
    if(p->f == null) return null;
    Node *q = p->f->pushDown();
    return q->set(p->lr(), null)->update()->splay();
}
// 删除第 k 个元素, 返回树根
Node* erase(Node *root, int k){
    Node *p = select(root, k)->splay();
    return merge(p->ch[0], p->ch[1]);
}
// 在 p 之前插入 q, 返回树根 
Node* insert(Node *p, Node *q){
    p->splay();
    if(p->ch[0] == null){
        p->set(0, q);
    }
    else{
        select(p, p->ch[0]->size)->splay(p)->set(1, q)->update();
    }
    p->update();
    return p;
}
// 在第 k 个元素前插入 p, 返回树根
Node* insert(Node *root, int k, Node *p){
    if(root == null) return p;
    if(k > root->size){
        return select(root, root->size)->splay()->set(1, p)->update();
    }
    else{
        return insert(select(root, k), p);
    }
}
// 给 [l, r] 区间加上一个数, 返回树根
Node* addVal(Node *root, int l, int r, int val){
    Node *p = range(root, l, r);
    p->exeAdd(val);
    return p->splay();
}
// 将 [l, r] 区间循环右移 t 位
Node* revolve(Node *root, int l, int r, int t){
    if(t == 0) return root;
    Node *p = range(root, r - t + 1, r);
    root = erase(p); p->f = null;
    return insert(root, l, p);
}
// 区间查询最大值
Node* queryMax(Node *root, int l, int r){
    Node *p = range(root, l, r);
    cout << p->mx << endl;
    return root;
}

/*
Splay模板 by zimpha
这道题目是POJ 3580 SuperMemo
实现了rot, splay, select, get_seq等基本功能
实现了区间反转，整段区间操作(+,覆盖之类的)，插入一个数，删除一个数
要获取区间[l, r]直接调用get_seq(l-1, r+1)即可。
每次使用前必须先调用init()函数
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=100000+10;
const int inf=~0U>>2;
struct node {
    node *ch[2], *p;
    int size, add, val, Min, rev;
    node () {size=0; val=inf;}
    bool d() {return this==p->ch[1];}
    void setc(node *c, int d) {ch[d]=c; c->p=this;}
    void markAdd(int _add) {
        add+=_add, val+=_add, Min+=_add;
    }
    void markRev() {
        rev^=1; swap(ch[0], ch[1]);
    }
    void update() {
        size=ch[0]->size+ch[1]->size+1;
        Min=min(val, min(ch[0]->Min, ch[1]->Min));
    }
}*null, *root;
node mem[MAXN*2], *stk[MAXN*2];
int A[MAXN], N, M, top;
inline void pushdown(node *t) {
    if (t==null) return;
    if (t->add) {
        if (t->ch[0]!=null) t->ch[0]->markAdd(t->add);
        if (t->ch[1]!=null) t->ch[1]->markAdd(t->add);
    }
    if (t->rev) {
        if (t->ch[0]!=null) t->ch[0]->markRev();
        if (t->ch[1]!=null) t->ch[1]->markRev();
    }
    t->add=t->rev=0;
}
inline node *new_node(int v) {
    node *ret=stk[--top];
    ret->val=v; ret->size=1; ret->Min=v; ret->add=0;
    ret->ch[0]=ret->ch[1]=ret->p=null;
    return ret;
}
inline void recycle(node *x) {
    stk[top++]=x;
}
inline node* rot(node *t) {
    node *p=t->p;
    pushdown(p); pushdown(t);
    int d=t->d();
    p->p->setc(t, p->d());
    p->setc(t->ch[!d], d);
    t->setc(p, !d);
    p->update();
    if (p==root) root=t;
    return t;
}
inline void splay(node *t, node *f) {
    for (pushdown(t); t->p!=f;) {
        if (t->p->p==f) rot(t);
        else t->d()==t->p->d() ? (rot(t->p), rot(t)) : (rot(t), rot(t));
    }
    t->update();
}
inline node *select(int k) {
    for (node *t=root;;) {
        pushdown(t);
        int c=t->ch[0]->size;
        if (k==c) return t;
        if (k>c) k-=c+1, t=t->ch[1];
        else t=t->ch[0];
    }
    return null;
}
inline node *get_seq(int l, int r) {
    node *L=select(l); splay(L, null);
    node *R=select(r); splay(R, root);
    return root->ch[1]->ch[0];
}
node *build_tree(int *l, int *r) {
    if (l>=r) return null;
    if (l+1==r) return new_node(*l);
    int *m=l+(r-l)/2;
    node *t=new_node(*m);
    t->setc(build_tree(l, m), 0);
    t->setc(build_tree(m+1, r), 1);
    t->update(); return t;
}
void init() {
    for (int i=0; i<2*MAXN; i++) stk[i]=mem+i; top=MAXN*2;
    null=new_node(inf); null->size=0; null->Min=inf;
    null->ch[0]=null->ch[1]=null->p=null;
    A[0]=A[N+1]=inf;
    root=build_tree(A, A+N+2);
}
void ADD() {
    int x, y, D; scanf("%d%d%d", &x, &y, &D);
    node *t=get_seq(x-1, y+1);
    t->markAdd(D); splay(t, null);
}
void REVERSE() {
    int x, y; scanf("%d%d", &x, &y);
    node *t=get_seq(x-1, y+1);
    t->markRev(); splay(t, null);
}
void REVOLVE() {
    int x, y, T; scanf("%d%d%d", &x, &y, &T);
    int n=y-x+1; T%=n; if (T==0) return;
    node *t=get_seq(x-1, x+n-T);
    t->p->setc(null, 0); splay(root->ch[1], null);
    get_seq(x+T-1, x+T);
    root->ch[1]->setc(t, 0); splay(t, null);
}
void INSERT() {
    int x, P; scanf("%d%d", &x, &P); A[0]=P;
    node *t=build_tree(A, A+1);
    get_seq(x, x+1);
    root->ch[1]->setc(t, 0);
    splay(t, null);
}
void DELETE() {
    int x; scanf("%d", &x);
    node *t=get_seq(x-1, x+1);
    t->p->setc(null, 0); splay(root->ch[1], null);
    recycle(t);
}
void MIN() {
    int x, y; scanf("%d%d", &x, &y);
    node *t=get_seq(x-1, y+1);
    printf("%d\n", t->Min);
}
int main() {
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%d", A+i);
    init();
    scanf("%d", &M);
    while (M--) {
        char CMD[20];
        scanf("%s", CMD);
        if (CMD[0]=='A') ADD();
        else if (CMD[0]=='I') INSERT();
        else if (CMD[0]=='D') DELETE();
        else if (CMD[0]=='M') MIN();
        else if (CMD[3]=='E') REVERSE();
        else if (CMD[3]=='O') REVOLVE();
    }
    return 0;
}