Splay树

资料:http://blog.csdn.net/luckcircle/article/details/73277977
HYSBZ - 3224
CE一整天

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define clr(a) memset((a),0,sizeof (a))
using namespace std;
const int maxn =  3e5+11;
struct Splay{
    int root,sz,n;
    int f[maxn],ch[maxn][2],key[maxn],cnt[maxn],size[maxn];
    void init(){
        sz=0;root=0;
        clr(f);clr(ch);clr(key);clr(cnt);clr(size);
    }
    void clear(int x){
        f[x]=0;
        ch[x][0]=ch[x][1]=0;
        key[x]=size[x]=cnt[x]=0;
    } 
    int get(int x){
        return ch[f[x]][1]==x;
    }
    void update(int x){
        size[x]=cnt[x]+size[ch[x][0]]+size[ch[x][1]];
    }
    void rotate(int x){
        int old=f[x],oldf=f[old],wh=get(x);
        ch[old][wh]=ch[x][wh^1];
        if(ch[old][wh]) f[ch[old][wh]]=old;
        ch[x][wh^1]=old;
        f[old]=x;
        if(oldf) ch[oldf][ch[oldf][1]==old]=x;
        f[x]=oldf;
        update(old);
        update(x);
    }
    void splay(int x){
        for(int fa;fa=f[x];rotate(x))
            if(f[fa]) rotate(get(x)==get(fa)?fa:x);
        root=x;
    }
    void insert(int x){
        if(!root){
            root=++sz;
            cnt[sz]=size[sz]=1;key[sz]=x;
            return ;
        }
        int now=root,fa=0;
        while(1){
            if(x==key[now]){
                cnt[now]++;
                update(now);
                splay(now);
                break;
            }
            fa=now;
            now=ch[now][x>key[now]];
            if(!now){
                ++sz;
                f[sz]=fa;ch[fa][x>key[fa]]=sz;
                size[sz]=cnt[sz]=1;
                key[sz]=x;
                update(fa);
                splay(sz);
                break;
            }
        }
    }
    int find(int x){
        int now=root,ans=0;
        while(1){
            if(x<key[now]) now=ch[now][0];
            else{
                ans+=size[ch[now][0]];
                if(x==key[now]){
                    splay(now);
                    return ans+1;
                }
                ans+=cnt[now];
                now=ch[now][1];
            }
        }
    }
    int findx(int x){
        int now=root;
        while(1){
            if(x<=size[ch[now][0]]) now=ch[now][0];
            else{
                x-=size[ch[now][0]];
                if(x<=cnt[now]){
                    splay(now);
                    return key[now];
                }
                x-=cnt[now];
                now=ch[now][1];
            }
        }
    }
    int pre(){
        int now=ch[root][0];
        while(ch[now][1]) now=ch[now][1];
        return now;
    }
    int nxt(){
        int now=ch[root][1];
        while(ch[now][0]) now=ch[now][0];
        return now;
    }
    void del(int x){
        int wh=find(x);
        if(cnt[root]>1){
            --cnt[root];
            update(root);
            return;
        }
        if(!ch[root][0]&&!ch[root][1]){
            clear(root);
            root=0;
            return;
        }
        if(!ch[root][0]){
            int oldroot=root;
            root=ch[oldroot][1];
            f[root]=0;
            clear(oldroot);
            return;
        }
        if(!ch[root][1]){
            int oldroot=root;
            root=ch[oldroot][0];
            f[root]=0;
            clear(oldroot);
            return;
        }
        int oldroot=root;
        int leftbig=pre();splay(leftbig);
        ch[root][1]=ch[oldroot][1];
        f[ch[root][1]]=root;
        clear(oldroot);
        update(root);
        return; 
    }
}splay;
int n; 
int main(){
    while(scanf("%d",&n)!=EOF){
        splay.init();
        int op,t;
        for(int i = 0; i < n; i++){
            scanf("%d%d",&op,&t);
            switch(op){
                case 1: splay.insert(t);break;
                case 2: splay.del(t);break;
                case 3: printf("%d\n",splay.find(t));break;
                case 4: printf("%d\n",splay.findx(t));break;
                case 5: splay.insert(t);printf("%d\n",splay.key[splay.pre()]);splay.del(t);break;
                case 6: splay.insert(t);printf("%d\n",splay.key[splay.nxt()]);splay.del(t);break;
            }
        }
    }
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+1111;
const int oo = 0x3f3f3f3f;
struct Splay{
    int root,tot;
    int a[maxn],st[maxn],top;
    int son[maxn][2],pre[maxn],val[maxn],sz[maxn];
    bool flip[maxn];
    int same[maxn],sum[maxn],maxl[maxn],maxr[maxn],maxm[maxn];
    void pu(int o){
        int lc,rc;
        lc=son[o][0];
        rc=son[o][1];
        sz[o]=sz[lc]+sz[rc]+1;
        sum[o]=sum[lc]+sum[rc]+val[o];
        maxl[o]=max(maxl[lc],sum[lc]+val[o]+max(maxl[rc],0));
        maxr[o]=max(maxr[rc],sum[rc]+val[o]+max(maxr[lc],0));
        maxm[o]=max(maxm[lc],maxm[rc]);
        maxm[o]=max(maxm[o],max(maxr[lc],0)+val[o]+max(maxl[rc],0));
    }
    void pd(int o){
        int lc=son[o][0];
        int rc=son[o][1];
        if(flip[o]){
            flip[o]=0;
            swap(son[o][0],son[o][1]);
            if(lc){
                flip[lc]^=1;
                swap(maxl[lc],maxr[lc]);
            }
            if(rc){
                flip[rc]^=1;
                swap(maxl[rc],maxr[rc]);
            }
        }
        if(same[o]!=-oo){
            if(lc){
                same[lc]=val[lc]=same[o];
                sum[lc]=sz[lc]*same[o];
                maxl[lc]=maxr[lc]=maxm[lc]=max(same[o],sum[lc]);
            }
            if(rc){
                same[rc]=val[rc]=same[o];
                sum[rc]=sz[rc]*same[o];
                maxl[rc]=maxr[rc]=maxm[rc]=max(same[o],sum[rc]);
            }
            same[o]=-oo;
        }
    }
    void node(int &o,int fa,int v){
        if(~top) o=st[top--];
        else o=++tot;
        flip[o]=0;
        son[o][0]=son[o][1]=0;
        pre[o]=fa;
        val[o]=sum[o]=maxl[o]=maxr[o]=maxm[o]=v;
        sz[o]=1;
        same[o]=-oo;
    }
    void build(int &o,int l,int r,int fa){
        if(l<=r){
            int m=l+r>>1;
            node(o,fa,a[m]);
            build(son[o][0],l,m-1,o);
            build(son[o][1],m+1,r,o);
            pu(o);
        }
    }
    void init(int n){
        top=-1;
        root=tot=0;
        son[0][0]=son[0][1]=pre[0]=val[0]=sz[0]=sum[0]=0;
        flip[0]=0;
        same[0]=maxl[0]=maxr[0]=maxm[0]=-oo;
        node(root,0,-oo);//root=1
        node(son[root][1],root,-oo);
        build(son[son[root][1]][0],1,n,son[root][1]);
        pu(son[root][1]);
        pu(root);
    }
    void rotate(int o,int wh){
        int fa,ffa;
        fa=pre[o];ffa=pre[fa];
        pd(fa);
        son[fa][!wh]=son[o][wh];
        pre[son[o][wh]]=fa;
        son[ffa][son[ffa][1]==fa]=o;
        pre[o]=ffa;
        son[o][wh]=fa;
        pre[fa]=o;
        pu(fa);
    }
    void splay(int o,int to){
        if(o!=to){
            pd(o);
            while(pre[o]!=to){
                if(son[pre[o]][0]==o) rotate(o,1);
                else rotate(o,0);
            }
            pu(o);
            if(!to) root=o;
        }
    }
    int select(int k){
        int o;
        pd(root);
        for(o=root;sz[son[o][0]]+1!=k;){
            if(sz[son[o][0]]+1>k) o=son[o][0];
            else{
                k-=sz[son[o][0]]+1;
                o=son[o][1];
            }
            pd(o);
        }
        return o;
    }
    int getsum(int x,int y){
        x=select(x-1);
        y=select(y+1);
        splay(x,0);
        splay(y,x);
        return sum[son[y][0]];
    }
    void recycle(int o){
        if(o){
            st[++top]=o;
            recycle(son[o][0]);
            recycle(son[o][1]);
        }
    }
    void kill(int x,int y){
        x=select(x-1);
        y=select(y+1);
        splay(x,0);
        splay(y,x);
        recycle(son[y][0]);
        son[y][0]=0;
        pu(y);
        pu(x);
    }
    void makeflip(int x,int y){
        x=select(x-1);
        y=select(y+1);
        splay(x,0);
        splay(y,x);
        y=son[y][0];
        flip[y]^=1;
        swap(maxl[y],maxr[y]);
    }
    void makesame(int x,int y,int v){
        int t;
        x=select(x-1);
        y=select(y+1);
        splay(x,0);
        splay(y,x);
        t=son[y][0];
        same[t]=val[t]=v;
        sum[t]=v*sz[t];
        maxl[t]=maxr[t]=maxm[t]=max(v,sum[t]);
        pu(y);
        pu(x);
    }
    int getmin(int o){
        pd(o);
        while(son[o][0]){
            o=son[o][0];
            pd(o);
        }
        return o;
    }
    void insert(int x,int cnt){
        int y;
        x=select(x);
        splay(x,0);
        y=getmin(son[x][1]);
        splay(y,x);
        build(son[y][0],1,cnt,y);
        pu(y); 
        pu(x);
    }
    int getmaxm(int x,int y){
        x=select(x-1);
        y=select(y+1);
        splay(x,0);
        splay(y,x);
        return maxm[son[y][0]];
    }
}splay;
int n,m,pos,cnt,val;
char str[100];
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d",&splay.a[i]);
        }
        splay.init(n);
        for(int i = 1; i <= m; i++){
            scanf("%s",str);
            if(str[0]=='G'){
                scanf("%d%d",&pos,&cnt);
                printf("%d\n",splay.getsum(pos+1,pos+cnt));
            }
            else if(str[2]=='X'){
                printf("%d\n",splay.getmaxm(2,splay.sz[splay.root]-1));
            }
            else if(str[0]=='I'){
                scanf("%d%d",&pos,&cnt);
                for(int j = 1; j <= cnt; j++){
                    scanf("%d",&splay.a[j]);
                }
                splay.insert(pos+1,cnt);
            }
            else if(str[0]=='D'){
                scanf("%d%d",&pos,&cnt);
                splay.kill(pos+1,pos+cnt);
            }
            else if(str[2]=='K'){
                scanf("%d%d%d",&pos,&cnt,&val);
                splay.makesame(pos+1,pos+cnt,val);
            }
            else if(str[0]=='R'){
                scanf("%d%d",&pos,&cnt);
                splay.makeflip(pos+1,pos+cnt);
            }
        }
    }
    return 0;
}

dalao的资料:http://blog.csdn.net/zeyu_king/article/details/42749139
http://blog.sina.com.cn/s/blog_6e63f59e0101bj9b.html
http://blog.csdn.net/Kirito_Acmer/article/details/51444990
http://blog.csdn.net/litble/article/details/74612868
http://sbp810050504.blog.51cto.com/2799422/1029553/
http://sbp810050504.blog.51cto.com/2799422/1027007

标签: 算法, 学习

添加新评论