hdu 5412 CRB and Queries Dynamic 구간 K-작은 트리 트리

제목: n개의 수를 주고 두 개의 조작이 있다.i번째 점의 값을 v2로 수정합니다.구간 내 k의 작은 수를 구하다
트리 그룹 + 균형 트리입니다.나는 두 개의 코드를 썼다. 트리 그룹 + SBT, 트리 그룹 + Treap 코드:
//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
"
,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
",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
" :: "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
",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
"
,res[ans]); } } } //printf("%.2lf
",1.0*(clock()-now)/CLOCKS_PER_SEC);
return 0; }

코드 2:
//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
" :: "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
",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
",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
"
,res[ans]); } } } return 0; }

좋은 웹페이지 즐겨찾기