【算法】Treap模板和SBT模板

SBT:http://blog.csdn.net/acceptedxukai/article/details/6921334
Treap:来源忘了。

有个可以优化的地方，就是将相同值合并为同一点，以后改了再放上来。
题目：hdu 5412
Treap版本1:

//author: CHC
//First Edit Time:    2015-08-20 12:15
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
class Treap {
    public:
        struct node {
            node *ch[2];
            int v,p,sz;
            node(int _v,node *_n){ v=_v; ch[0]=ch[1]=_n; p=rand(); sz=1; }
            void update(){sz=ch[0]->sz+ch[1]->sz+1;}
            void fixch(node *left,node *right){ch[0]=left;ch[1]=right;}
        };
        node *root,*null;
        Treap(){
            null=new node(0,0);
            null->fixch(null,null); null->sz=0;
            root=null;
        }
        void rotate(node *&t,bool d){
            node *_t=t->ch[d];
            t->ch[d]=_t->ch[!d];
            _t->ch[!d]=t;
            t->update();
            _t->update();
            t=_t;
        }
        void __insert(node *&t,int val){
            if(t==null){
                t=new node(val,null);
                return ;
            }
            bool d=(t->v < val);
            __insert(t->ch[d],val);
            if(t->ch[d]->p < t->p)rotate(t,d);
            t->update();
        }
        void __del(node *&t,int val){
            if(t==null)return ;
            if(t->v==val){
                node *tmp=t;
                if(t->ch[0]==null){
                    t=t->ch[1];
                    delete tmp;
                    return ;
                }
                if(t->ch[1]==null){
                    t=t->ch[0];
                    delete tmp;
                    return ;
                }
                bool d=t->ch[1]->p < t->ch[0]->p;
                rotate(t,d);
                __del(t->ch[!d],val);
            }
            else {
                bool d=(t->v < val);
                __del(t->ch[d],val);
            }
            t->update();
        }
        int __rank(node *t,int val){
            if(t==null)return 0;
            if(t->v <= val)return t->ch[0]->sz+1+__rank(t->ch[1],val);
            //return t->ch[1]->sz+1+__rank(t->ch[0],val);
            return __rank(t->ch[0],val);
        }
        void __clean(node *&t){
            if(t==null)return ;
            if(t->ch[0]!=null)__clean(t->ch[0]);
            if(t->ch[1]!=null)__clean(t->ch[1]);
            delete t;
            t=null;
        }
        void insert(int val){ __insert(root,val); }
        void del(int val){ __del(root,val); }
        int rank(int val){ return __rank(root,val);}
        void clean(){ __clean(root); }
        ~Treap(){ clean(); delete null; }
}tr[MAXN];
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
int A[MAXN],n;
void Add(int pos,int v){
    while(pos<=n){
        tr[pos].insert(v);
        pos+=pos&-pos;
    }
}
void Del(int pos,int v){
    while(pos<=n){
        tr[pos].del(v);
        pos+=pos&-pos;
    }
}
int Sum(int pos,int v){
    int cnt=0;
    while(pos>0){
        cnt+=tr[pos].rank(v);
        pos-=pos&-pos;
    }
    return cnt;
}
struct Q {
    int type,l,r,v;
}cs[MAXN];
int res[MAXN*2];
int main()
{
    //int size = 256 << 20; // 256MB  
    //char *p = (char*)malloc(size) + size;  
    //__asm__("movl %0, %%esp\n" :: "r"(p));
    //freopen("1007.in","r",stdin);
    //freopen("10071.out","w",stdout);
    while(~scanf("%d",&n)){
        res[0]=0;
        for(int i=1;i<=n;i++)scanf("%d",&A[i]),res[++res[0]]=A[i];
        int q;
        //printf("%d\n",query(1,n,1,1,n,4));
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d",&cs[i].type);
            if(cs[i].type==1){
                scanf("%d%d",&cs[i].l,&cs[i].v);
                res[++res[0]]=cs[i].v;
            }
            else {
                scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].v);
            }
        }
        sort(res+1,res+1+res[0]);
        res[0]=unique(res+1,res+1+res[0])-res-1;
        //printf("res0:%d\n",res[0]);
        //for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
        //puts("");
        for(int i=1;i<=n;i++){
            A[i]=lower_bound(res+1,res+1+res[0],A[i])-res;
        }
        //build(1,n,1);
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                cs[i].v=lower_bound(res+1,res+1+res[0],cs[i].v)-res;
            }
        }
        for(int i=0;i<=n;i++)tr[i].clean();
        for(int i=1;i<=n;i++){
            Add(i,A[i]);
        }
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                //while(A[cs[i].l]<=0||A[cs[i].l]>res[0]);
                Del(cs[i].l,A[cs[i].l]);
                Add(cs[i].l,cs[i].v);
                A[cs[i].l]=cs[i].v;
            //update(1,n,1,cs[i].l,cs[i].v);
            }
            else {
                int l=1,r=res[0],ans=res[0];
                while(l<=r){
                    int mid=(l+r)>>1;
                    int t=Sum(cs[i].r,mid)-Sum(cs[i].l-1,mid);
                    //if(query(1,n,1,cs[i].l,cs[i].r,mid)>=cs[i].v){
                    if(t>=cs[i].v){
                        ans=mid;
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                printf("%d\n",res[ans]);
            }
        }
    }
    return 0;
}

Treap版本2:

//author: CHC
//First Edit Time:	2015-08-21 21:55
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct Treap {
    Treap *ch[2];
    int v,p,sz;
    void update(){sz=ch[0]->sz+ch[1]->sz+1;}
}tr[MAXN*30];
Treap *root[MAXN];
struct TreapOp {
    public:
    Treap * null;
    int tot;
    TreapOp(){ null=&tr[0]; }
    void init(){
        tot=0;
        null=&tr[0];
        Inittr(0,0);
        tr[0].sz=0;
        for(int i=0;i<MAXN;i++)root[i]=null;
    }
    void Inittr(int x,int _v){
        tr[x].v=_v;tr[x].ch[0]=tr[x].ch[1]=null;tr[x].sz=1;tr[x].p=rand();
    }
    void rotate(Treap *&t,bool d){
        Treap *_t=t->ch[d];
        t->ch[d]=_t->ch[!d];
        _t->ch[!d]=t;
        t->update();
        _t->update();
        t=_t;
    }
    void __insert(Treap *&t,int val){
        if(t==null){
            //t->Init(val);
            //t=new node(val,null);
            t=&tr[++tot];
            Inittr(tot,val);
            return ;
        }
        bool d=(t->v < val);
        __insert(t->ch[d],val);
        if(t->ch[d]->p < t->p)rotate(t,d);
        t->update();
    }
    void __del(Treap *&t,int val){
        if(t==null)return ;
        if(t->v==val){
            if(t->ch[0]==null){
                t=t->ch[1];
                return ;
            }
            if(t->ch[1]==null){
                t=t->ch[0];
                return ;
            }
            bool d=t->ch[1]->p < t->ch[0]->p;
            rotate(t,d);
            __del(t->ch[!d],val);
        }
        else {
            bool d=(t->v < val);
            __del(t->ch[d],val);
        }
        t->update();
    }
    int __rank(Treap *t,int val){
        if(t==null)return 0;
        if(t->v <= val)return t->ch[0]->sz+1+__rank(t->ch[1],val);
        //return t->ch[1]->sz+1+__rank(t->ch[0],val);
        return __rank(t->ch[0],val);
    }
    void insert(int x,int val){__insert(root[x],val);}
    void del(int x,int val){__del(root[x],val);}
    int rank(int x,int val){return __rank(root[x],val);}
}treap;
int n,A[MAXN];
void Add(int x,int v){
    while(x<=n){
        treap.insert(x,v);
        x+=x&-x;
    }
}
void Del(int x,int v){
    while(x<=n){
        treap.del(x,v);
        x+=x&-x;
    }
}
int Sum(int x,int val){
    int cnt=0;
    while(x>0){
        cnt+=treap.rank(x,val);
        x-=x&-x;
    }
    return cnt;
}
struct Q {
    int type,l,r,v;
}cs[MAXN];
int res[MAXN*2];
int main()
{
    //int size = 256 << 20; // 256MB  
    //char *p = (char*)malloc(size) + size;  
    //__asm__("movl %0, %%esp\n" :: "r"(p));
    //freopen("1007.in","r",stdin);
    //freopen("10071.out","w",stdout);
    while(~scanf("%d",&n)){
        res[0]=0;
        for(int i=1;i<=n;i++)scanf("%d",&A[i]),res[++res[0]]=A[i];
        int q;
        //printf("%d\n",query(1,n,1,1,n,4));
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d",&cs[i].type);
            if(cs[i].type==1){
                scanf("%d%d",&cs[i].l,&cs[i].v);
                res[++res[0]]=cs[i].v;
            }
            else {
                scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].v);
            }
        }
        sort(res+1,res+1+res[0]);
        res[0]=unique(res+1,res+1+res[0])-res-1;
        //printf("res0:%d\n",res[0]);
        //for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
        //puts("");
        for(int i=1;i<=n;i++){
            A[i]=lower_bound(res+1,res+1+res[0],A[i])-res;
        }
        //build(1,n,1);
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                cs[i].v=lower_bound(res+1,res+1+res[0],cs[i].v)-res;
            }
        }
        treap.init();
        for(int i=1;i<=n;i++){
            Add(i,A[i]);
        }
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                //while(A[cs[i].l]<=0||A[cs[i].l]>res[0]);
                Del(cs[i].l,A[cs[i].l]);
                Add(cs[i].l,cs[i].v);
                A[cs[i].l]=cs[i].v;
            //update(1,n,1,cs[i].l,cs[i].v);
            }
            else {
                int l=1,r=res[0],ans=res[0];
                while(l<=r){
                    int mid=(l+r)>>1;
                    int t=Sum(cs[i].r,mid)-Sum(cs[i].l-1,mid);
                    //if(query(1,n,1,cs[i].l,cs[i].r,mid)>=cs[i].v){
                    if(t>=cs[i].v){
                        ans=mid;
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                printf("%d\n",res[ans]);
            }
        }
    }
    return 0;
}

SBT:

//author: CHC
//First Edit Time:	2015-08-20 14:10
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
#include <time.h>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
struct SBT
{
    int left,right,size,key;
    void Init()
    {
        left=right=0;
        size=1;
    }
}tree[MAXN*30];
int tot,root[MAXN<<2],n;
void left_rotate(int &x)//左旋
{
    int y=tree[x].right;
    tree[x].right=tree[y].left;
    tree[y].left=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void right_rotate(int &x)//右旋
{
    int y=tree[x].left;
    tree[x].left=tree[y].right;
    tree[y].right=x;
    tree[y].size=tree[x].size;
    tree[x].size=tree[tree[x].left].size+tree[tree[x].right].size+1;
    x=y;
}
void maintain(int &x,int flag)
{
    if(flag==0)
    {
        if(tree[tree[tree[x].left].left].size > tree[tree[x].right].size)
            right_rotate(x);
        else if(tree[tree[tree[x].left].right].size > tree[tree[x].right].size)
            left_rotate(tree[x].left),right_rotate(x);
        else return;
    }
    else
    {
        if(tree[tree[tree[x].right].right].size > tree[tree[x].left].size)
            left_rotate(x);
        else if(tree[tree[tree[x].right].left].size > tree[tree[x].left].size)
            right_rotate(tree[x].right),left_rotate(x);
        else return;
    }
    maintain(tree[x].left,0);
    maintain(tree[x].right,1);
    maintain(x,0);
    maintain(x,1);
}
//插入元素，相同元素放在右子树中
void insert(int &x,int key)
{
    if(x==0)
    {
        x=++tot;
        tree[x].Init();
        tree[x].key=key;
    }
    else
    {
        tree[x].size++;
        if(key<tree[x].key)insert(tree[x].left,key);
        else insert(tree[x].right,key);
        maintain(x,key>=tree[x].key);
    }
}
//删除key值的元素
int del(int &x,int key)
{
    if(!x)return 0;
    tree[x].size--;
    if(key==tree[x].key || (key<tree[x].key&&tree[x].left==0)
            || (key>tree[x].key&&tree[x].right==0))
    {
        if(tree[x].left && tree[x].right)
        {
            int p=del(tree[x].left,key+1);
            tree[x].key=tree[p].key;
            return p;
        }
        else
        {
            int p=x;
            x=tree[x].left+tree[x].right;
            return p;
        }
    }
    else return del(key<tree[x].key?tree[x].left:tree[x].right,key);
}
int _rank(int x,int val){
    if(x==0)return 0;
    if(tree[x].key<=val)return tree[tree[x].left].size+1+_rank(tree[x].right,val);
    return _rank(tree[x].left,val);
}
void print(int x,int d){
    if(!x)return ;
    printf("%d %d\n",tree[x].key,d);
    print(tree[x].left,d+1);print(tree[x].right,d+1);
}
int A[MAXN];
void Add(int x,int v){
    while(x<=n){
        //printf("x:%d\n",x);
        insert(root[x],v);
        x+=x&-x;
    }
}
void Del(int x,int v){
    while(x<=n){
        del(root[x],v);
        x+=x&-x;
    }
}
int Sum(int x,int v){
    int cnt=0;
    while(x>0){
        cnt+=_rank(root[x],v);
        x-=x&-x;
    }
    return cnt;
}
struct Q {
    int type,l,r,v;
}cs[MAXN];
int res[MAXN*2];
int main()
{
    //int size = 256 << 20; // 256MB  
    //char *p = (char*)malloc(size) + size;  
    //__asm__("movl %0, %%esp\n" :: "r"(p));
    //freopen("1007.in","r",stdin);
    //freopen("10071.out","w",stdout);
    //time_t now=clock();
    int q;
    while(~scanf("%d",&n)){
        memset(root,0,sizeof(root));
        tot=0;
        res[0]=0;
        for(int i=1;i<=n;i++)scanf("%d",&A[i]),res[++res[0]]=A[i];
        scanf("%d",&q);
        for(int i=0;i<q;i++){
            scanf("%d",&cs[i].type);
            if(cs[i].type==1){
                scanf("%d%d",&cs[i].l,&cs[i].v);
                res[++res[0]]=cs[i].v;
            }
            else {
                scanf("%d%d%d",&cs[i].l,&cs[i].r,&cs[i].v);
            }
        }
        sort(res+1,res+1+res[0]);
        res[0]=unique(res+1,res+1+res[0])-res-1;
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                cs[i].v=lower_bound(res+1,res+1+res[0],cs[i].v)-res;
            }
        }
        //printf("res0:%d\n",res[0]);
        //for(int i=1;i<=res[0];i++)printf("%d ",res[i]);
        //puts("");
        for(int i=1;i<=n;i++)A[i]=lower_bound(res+1,res+1+res[0],A[i])-res;
        //for(int i=1;i<=n;i++)printf("%d ",A[i]);
        //puts("");
        //build(1,n,1);
        //print(root[1],0);
        //puts("here__");
        for(int i=1;i<=n;i++){
            Add(i,A[i]);
        }
        //puts("here");
        for(int i=0;i<q;i++){
            if(cs[i].type==1){
                //update(1,n,1,cs[i].l,cs[i].v);
                Del(cs[i].l,A[cs[i].l]);
                Add(cs[i].l,cs[i].v);
                A[cs[i].l]=cs[i].v;
            }
            else {
                int l=1,r=res[0],ans=res[0];
                while(l<=r){
                    int mid=(l+r)>>1;
                    int t=Sum(cs[i].r,mid)-Sum(cs[i].l-1,mid);
                    if(t>=cs[i].v){
                        ans=mid;
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                printf("%d\n",res[ans]);
            }
        }
    }
    //printf("%.2lf\n",1.0*(clock()-now)/CLOCKS_PER_SEC);
    return 0;
}