三大平衡树题中的第二道……

果然文艺啊，轻音体柔易推倒，果然是萝莉

很明显伸展树辣！

代码：

/**************************************************************
    Problem: 3223
    User: danihao123
    Language: C++
    Result: Accepted
    Time:1788 ms
    Memory:3188 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cctype>
using namespace std;
const int maxn=100000;
struct Node{
    int v,s;
    bool lazy;
    Node* ch[2];
    int cmp(int x) const{
        int d=x-ch[0]->s;
        if(d==1)
            return -1;
        else
            return d<=0?0:1;
    }
    void maintain(){
        s=1+ch[0]->s+ch[1]->s;
    }
    void pushdown(){
        if(lazy){
            lazy=false;
            swap(ch[0],ch[1]);
            ch[0]->lazy=!(ch[0]->lazy);
            ch[1]->lazy=!(ch[1]->lazy);
        }
    }
};
void rotate(Node* &o,int d){
    Node* k=o->ch[d^1];
    o->ch[d^1]=k->ch[d];
    k->ch[d]=o;
    o->maintain();
    k->maintain();
    o=k;
}
void splay(Node* &o,int k){
    o->pushdown();
    int d=o->cmp(k);
    if(d==1)
        k-=(o->ch[0])->s+1;
    if(d!=-1){
        Node* p=o->ch[d];
        p->pushdown();
        int d2=p->cmp(k),k2=k;
        if(d2!=0)
            k2-=p->ch[0]->s+1;
        if(d2!=-1){
            splay(p->ch[d2],k2);
            if(d==d2)
                rotate(o,d^1);
            else
                rotate(o->ch[d],d);
        }
        rotate(o,d^1);
    }
}
Node* null=new Node();
// merge,left<right
Node* merge(Node* l,Node* r){
    splay(l,l->s);
    l->ch[1]=r;
    l->maintain();
    return l;
}
void split(Node* o,int k,Node* &l,Node* &r){
    splay(o,k);
    l=o;
    r=o->ch[1];
    o->ch[1]=null;
    l->maintain();
}
Node* root;
Node set[maxn];
int cnt=0;
Node* build_tree(int size){
    if(!size)
        return null;
    Node* L=build_tree(size/2);
    Node* o=&set[cnt++];
    o->v=cnt;
    o->ch[0]=L;
    o->ch[1]=build_tree(size-size/2-1);
    o->s=0;
    o->lazy=false;
    o->maintain();
    return o;
}
inline void init(int n){
    null->v=0;
    null->s=0;
    root=build_tree(n);
}
queue<int> ans;
void print(Node* o){
    if(o!=null){
        o->pushdown();
        print(o->ch[0]);
        ans.push(o->v);
        print(o->ch[1]);
    }
}
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
    register int n,m,u,v;
    n=readint();
    m=readint();
    init(n);
    bool nex=false;
    while(m--){
        u=readint();
        v=readint();
        Node *l,*mid,*r,*o;
        if(u==1){
            split(root,v,l,r);
            l->lazy^=1;
            root=merge(l,r);
        }else{
            split(root,u-1,l,o);
            split(o,v-u+1,mid,r);
            mid->lazy^=1;
            root=merge(merge(l,mid),r);
        }
    }
    print(root);
    while(!ans.empty()){
        u=ans.front();
        ans.pop();
        if(nex)
            putchar(' ');
        writeint(u);
        nex=true;
    }
//  putchar('\n');
    return 0;
}

• 相关文章
• 全局相关文章