Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

感谢陈启峰大牛的Size Balanced Tree，贴AC代码，顺便放出模板~~~大家共享吧

Posted by yzhw at 2009-09-26 13:36:25 on Problem 2761

Source Code

Problem: 2761  User: yzhw 
Memory: 3960K  Time: 3938MS 
Language: G++  Result: Accepted 

Source Code 
# include <iostream>
using namespace std;
# include <cstdio>
# include <cstring>
# include <cstdlib>

template<typename Type>
struct SBNode{
    int   size;
    Type  key;
    SBNode<Type>* lchild, *rchild;
    SBNode(){}
    SBNode( SBNode<Type>*l, SBNode<Type>*r, int s, Type k ):
        lchild(l), rchild(r), size(s), key(k) {}
};

template<typename Type>
class SBTree{
    private:
        SBNode<Type>* root;
        SBNode<Type>* _null;
        
        void left_rotate ( SBNode<Type>*& root );
        void right_rotate( SBNode<Type>*& root );
        void maintain( SBNode<Type>*& root, bool style );
        void insert( SBNode<Type>*& root, Type key );
        void erase ( SBNode<Type>*& root, Type key );
        void clear ( SBNode<Type>* root );
        void travel( SBNode<Type>* root );
        
    public:
        SBTree ();
        ~SBTree();
        
        void insert( Type key );       //  插入元素 
        void erase ( Type key );       //  删除元素
        Type get_rank( int k  );       //  获得第 k 个元素 
        Type get_min();                //  获得最小元素
        Type get_max();                //  获得最大元素
        void clear();                  //  清空 
        void travel();                 //  遍历 
};

template<typename Type>
Type SBTree<Type>::get_rank( int k ){
    SBNode<Type>* tmp= root;
	while(true)
	{
		if(tmp->lchild&&tmp->lchild->size+1==k) break;
		else if(tmp->lchild&&k<=tmp->lchild->size) tmp=tmp->lchild;
		else 
		{
			k=k-(tmp->lchild?tmp->lchild->size:0)-1;
			tmp=tmp->rchild;
		}
	}
    return tmp->key;
}

template<typename Type>
void SBTree<Type>::clear( SBNode<Type>* root ){
    if( root!= _null ){
        clear( root->lchild );
        clear( root->rchild );
        delete root; }
}

template<typename Type>
void SBTree<Type>::clear(){
    clear(root); delete _null; }

template<typename Type>
void SBTree<Type>::travel( SBNode<Type>* root ){
    if( root!= _null ){
        travel( root->lchild );
        cout << root->key << "  ";
        travel( root->rchild ); }
}

template<typename Type>
void SBTree<Type>::travel(){
    travel( root ); }

template<typename Type>
Type SBTree<Type>::get_min(){
    if( root== _null ) return Type();
    SBNode<Type>* tmp= root;
    while( tmp->lchild!= _null ) tmp= tmp->lchild;
    return tmp->key;
}

template<typename Type>
Type SBTree<Type>::get_max(){
    if( root== _null ) return Type();
    SBNode<Type>* tmp= root;
    while( tmp->rchild!= _null ) tmp= tmp->rchild;
    return tmp->key;
}

template<typename Type>
void SBTree<Type>::erase( Type key ){
    erase( root, key ); }

template<typename Type>
void SBTree<Type>::erase( SBNode<Type>*& root, Type key ){
    if( root== _null ) return;    root->size--;
    if( root->key== key ){
        SBNode<Type>* tmp;
        if( root->lchild!= _null && root->rchild== _null ){
            tmp= root;  root= tmp->lchild; delete tmp; }
        else if( root->lchild== _null && root->rchild== _null ){
            tmp= root; root= _null; delete tmp; }
        else {
            tmp= root->rchild; 
            while( tmp->lchild!= _null ) tmp= tmp->lchild;
            root->key= tmp->key; erase( root->rchild, tmp->key );}
    }
    else if( key< root->key ) erase( root->lchild, key );
    else erase( root->rchild, key );
}

template<typename Type>
void SBTree<Type>::insert( SBNode<Type>*& root, Type key ){
    if( root== _null ){
     root= new SBNode<Type>( _null, _null, 1, key ); return; }
    root->size++;
    if( key< root->key ) insert( root->lchild, key );
    else                 insert( root->rchild, key );
    maintain( root, key>= root->key );
}

template<typename Type>
void SBTree<Type>::insert( Type key ){
    insert( root, key ); }

template<typename Type>
SBTree<Type>::SBTree(){
    _null= new SBNode<Type>();
    root= _null; 
    root->lchild= root->rchild= _null;
    root->size= 0;
}

template<typename Type>
SBTree<Type>::~SBTree(){
    clear();
}

template<typename Type>
void SBTree<Type>::left_rotate( SBNode<Type>*& root ){
    SBNode<Type>* tmp= root->rchild;
    root->rchild= tmp->lchild;  tmp->lchild= root;
    tmp->size= root->size;
    root->size= root->lchild->size+ root->rchild->size+ 1;
    root= tmp;
}

template<typename Type>
void SBTree<Type>::right_rotate( SBNode<Type>*& root ){
    SBNode<Type>* tmp= root->lchild;
    root->lchild= tmp->rchild;  tmp->rchild= root;
    tmp->size= root->size;
    root->size= root->lchild->size+ root->rchild->size+ 1;
    root= tmp;
}

template<typename Type>
void SBTree<Type>::maintain( SBNode<Type>*& root, bool style ){
    if( root== _null ) return;
    if( !style ){
        if( root->lchild->lchild->size> root->rchild->size )
        right_rotate( root );
        else if( root->lchild->rchild->size> root->rchild->size ){
            left_rotate( root->lchild );
            right_rotate( root );
           }else return;
        }
    else {
        if( root->rchild->rchild->size> root->lchild->size )
        left_rotate( root );
        else if( root->rchild->lchild->size> root->lchild->size ){
            right_rotate( root->rchild );
            left_rotate( root ); 
        }else return;
    }
   maintain(root->lchild, false);  maintain(root->rchild, true);
   maintain(root, false);          maintain(root, true);
}
//start
struct ques
{
	int s,e;
	int id;
	int q;
	int ans;
}list[50001];
int cmp(const void *a,const void *b)
{
	ques *aa=(ques *)a;
	ques *bb=(ques *)b;
	if(aa->s!=bb->s) return aa->s-bb->s;
	else return aa->e-bb->e;
}
int cmp1(const void *a,const void *b)
{
	ques *aa=(ques *)a;
	ques *bb=(ques *)b;
	return aa->id-bb->id;
}

int main()
{
	SBTree<int> refer;
	int num[100001];
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
	    scanf("%d",num+i);
	
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d %d",&list[i].s,&list[i].e,&list[i].q);
		list[i].id=i;
	}
	qsort(list+1,m,sizeof(ques),cmp);
	for(int j=list[1].s;j<=list[1].e;j++)
		refer.insert(num[j]);

	list[1].ans=refer.get_rank(list[1].q);
	for(int i=2;i<=m;i++)
	{
		if(list[i].s>=list[i-1].e)//区间错开
		{
			for(int j=list[i-1].s;j<=list[i-1].e;j++)
				refer.erase(num[j]);
			for(int j=list[i].s;j<=list[i].e;j++)
				refer.insert(num[j]);
		}
		else if(list[i].s<=list[i-1].e&&list[i].e>list[i-1].e)//区间部分包含
		{
			for(int j=list[i-1].e+1;j<=list[i].e;j++)
				refer.insert(num[j]);
			for(int j=list[i-1].s;j<list[i].s;j++)
				refer.erase(num[j]);
		}
		else //子集
		{
			for(int j=list[i-1].s;j<list[i].s;j++)
				refer.erase(num[j]);
			for(int j=list[i].e+1;j<=list[i-1].e;j++)
				refer.erase(num[j]);
		}
		list[i].ans=refer.get_rank(list[i].q);
	}
	qsort(list+1,m,sizeof(ques),cmp1);
	for(int i=1;i<=m;i++)
		printf("%d\n",list[i].ans);
	return 0;


}

Followed by:

再给一个这个问题的伸展树版本吧，好像很搓。。。。5S多过的。。还是SBT强啊。。 (7396) yzhw 2009-09-26 14:12:01
- Re:我也发一个Splay伸展树版本的，3204ms过的，貌似常数还算小，静态数组做的 (6405) mq_miqing 2010-02-21 15:04:30
  - Re:我也发一个Splay伸展树版本的，3204ms过的，貌似常数还算小，静态数组做的 (14) Master_Chivu 2010-08-23 17:53:29
  - 那个“pg:=@right[fa[g]]”中@是神马运算符？ (30) MyIdea 2011-08-01 10:48:18
    - Re:那个“pg:=@right[fa[g]]”中@是神马运算符？ (93) Hoblovski 2014-05-13 19:34:03
  - 那个“pg:=@right[fa[g]]”中@是神马运算符？ (2) MyIdea 2011-08-01 10:48:26
  - Re:我也发一个Splay伸展树版本的，3204ms过的，貌似常数还算小，静态数组做的 (6903) dyh495768138 2014-01-26 15:44:53
Re:感谢陈启峰大牛的Size Balanced Tree，贴AC代码，顺便放出模板~~~大家共享吧 (7623) jiyanmoyu 2010-07-18 15:47:11

Post your reply here:

User ID:
Password:
Title:

Content:

> Source Code
> 
> Problem: 2761  User: yzhw 
> Memory: 3960K  Time: 3938MS 
> Language: G++  Result: Accepted 
> 
> Source Code 
> # include <iostream>
> using namespace std;
> # include <cstdio>
> # include <cstring>
> # include <cstdlib>
> 
> template<typename Type>
> struct SBNode{
>     int   size;
>     Type  key;
>     SBNode<Type>* lchild, *rchild;
>     SBNode(){}
>     SBNode( SBNode<Type>*l, SBNode<Type>*r, int s, Type k ):
>         lchild(l), rchild(r), size(s), key(k) {}
> };
> 
> template<typename Type>
> class SBTree{
>     private:
>         SBNode<Type>* root;
>         SBNode<Type>* _null;
>         
>         void left_rotate ( SBNode<Type>*& root );
>         void right_rotate( SBNode<Type>*& root );
>         void maintain( SBNode<Type>*& root, bool style );
>         void insert( SBNode<Type>*& root, Type key );
>         void erase ( SBNode<Type>*& root, Type key );
>         void clear ( SBNode<Type>* root );
>         void travel( SBNode<Type>* root );
>         
>     public:
>         SBTree ();
>         ~SBTree();
>         
>         void insert( Type key );       //  插入元素 
>         void erase ( Type key );       //  删除元素
>         Type get_rank( int k  );       //  获得第 k 个元素 
>         Type get_min();                //  获得最小元素
>         Type get_max();                //  获得最大元素
>         void clear();                  //  清空 
>         void travel();                 //  遍历 
> };
> 
> template<typename Type>
> Type SBTree<Type>::get_rank( int k ){
>     SBNode<Type>* tmp= root;
> 	while(true)
> 	{
> 		if(tmp->lchild&&tmp->lchild->size+1==k) break;
> 		else if(tmp->lchild&&k<=tmp->lchild->size) tmp=tmp->lchild;
> 		else 
> 		{
> 			k=k-(tmp->lchild?tmp->lchild->size:0)-1;
> 			tmp=tmp->rchild;
> 		}
> 	}
>     return tmp->key;
> }
> 
> template<typename Type>
> void SBTree<Type>::clear( SBNode<Type>* root ){
>     if( root!= _null ){
>         clear( root->lchild );
>         clear( root->rchild );
>         delete root; }
> }
> 
> template<typename Type>
> void SBTree<Type>::clear(){
>     clear(root); delete _null; }
> 
> template<typename Type>
> void SBTree<Type>::travel( SBNode<Type>* root ){
>     if( root!= _null ){
>         travel( root->lchild );
>         cout << root->key << "  ";
>         travel( root->rchild ); }
> }
> 
> template<typename Type>
> void SBTree<Type>::travel(){
>     travel( root ); }
> 
> template<typename Type>
> Type SBTree<Type>::get_min(){
>     if( root== _null ) return Type();
>     SBNode<Type>* tmp= root;
>     while( tmp->lchild!= _null ) tmp= tmp->lchild;
>     return tmp->key;
> }
> 
> template<typename Type>
> Type SBTree<Type>::get_max(){
>     if( root== _null ) return Type();
>     SBNode<Type>* tmp= root;
>     while( tmp->rchild!= _null ) tmp= tmp->rchild;
>     return tmp->key;
> }
> 
> template<typename Type>
> void SBTree<Type>::erase( Type key ){
>     erase( root, key ); }
> 
> template<typename Type>
> void SBTree<Type>::erase( SBNode<Type>*& root, Type key ){
>     if( root== _null ) return;    root->size--;
>     if( root->key== key ){
>         SBNode<Type>* tmp;
>         if( root->lchild!= _null && root->rchild== _null ){
>             tmp= root;  root= tmp->lchild; delete tmp; }
>         else if( root->lchild== _null && root->rchild== _null ){
>             tmp= root; root= _null; delete tmp; }
>         else {
>             tmp= root->rchild; 
>             while( tmp->lchild!= _null ) tmp= tmp->lchild;
>             root->key= tmp->key; erase( root->rchild, tmp->key );}
>     }
>     else if( key< root->key ) erase( root->lchild, key );
>     else erase( root->rchild, key );
> }
> 
> template<typename Type>
> void SBTree<Type>::insert( SBNode<Type>*& root, Type key ){
>     if( root== _null ){
>      root= new SBNode<Type>( _null, _null, 1, key ); return; }
>     root->size++;
>     if( key< root->key ) insert( root->lchild, key );
>     else                 insert( root->rchild, key );
>     maintain( root, key>= root->key );
> }
> 
> template<typename Type>
> void SBTree<Type>::insert( Type key ){
>     insert( root, key ); }
> 
> template<typename Type>
> SBTree<Type>::SBTree(){
>     _null= new SBNode<Type>();
>     root= _null; 
>     root->lchild= root->rchild= _null;
>     root->size= 0;
> }
> 
> template<typename Type>
> SBTree<Type>::~SBTree(){
>     clear();
> }
> 
> template<typename Type>
> void SBTree<Type>::left_rotate( SBNode<Type>*& root ){
>     SBNode<Type>* tmp= root->rchild;
>     root->rchild= tmp->lchild;  tmp->lchild= root;
>     tmp->size= root->size;
>     root->size= root->lchild->size+ root->rchild->size+ 1;
>     root= tmp;
> }
> 
> template<typename Type>
> void SBTree<Type>::right_rotate( SBNode<Type>*& root ){
>     SBNode<Type>* tmp= root->lchild;
>     root->lchild= tmp->rchild;  tmp->rchild= root;
>     tmp->size= root->size;
>     root->size= root->lchild->size+ root->rchild->size+ 1;
>     root= tmp;
> }
> 
> template<typename Type>
> void SBTree<Type>::maintain( SBNode<Type>*& root, bool style ){
>     if( root== _null ) return;
>     if( !style ){
>         if( root->lchild->lchild->size> root->rchild->size )
>         right_rotate( root );
>         else if( root->lchild->rchild->size> root->rchild->size ){
>             left_rotate( root->lchild );
>             right_rotate( root );
>            }else return;
>         }
>     else {
>         if( root->rchild->rchild->size> root->lchild->size )
>         left_rotate( root );
>         else if( root->rchild->lchild->size> root->lchild->size ){
>             right_rotate( root->rchild );
>             left_rotate( root ); 
>         }else return;
>     }
>    maintain(root->lchild, false);  maintain(root->rchild, true);
>    maintain(root, false);          maintain(root, true);
> }
> //start
> struct ques
> {
> 	int s,e;
> 	int id;
> 	int q;
> 	int ans;
> }list[50001];
> int cmp(const void *a,const void *b)
> {
> 	ques *aa=(ques *)a;
> 	ques *bb=(ques *)b;
> 	if(aa->s!=bb->s) return aa->s-bb->s;
> 	else return aa->e-bb->e;
> }
> int cmp1(const void *a,const void *b)
> {
> 	ques *aa=(ques *)a;
> 	ques *bb=(ques *)b;
> 	return aa->id-bb->id;
> }
> 
> int main()
> {
> 	SBTree<int> refer;
> 	int num[100001];
> 	int n,m;
> 	scanf("%d %d",&n,&m);
> 	for(int i=1;i<=n;i++)
> 	{
> 	    scanf("%d",num+i);
> 	
> 	}
> 	for(int i=1;i<=m;i++)
> 	{
> 		scanf("%d %d %d",&list[i].s,&list[i].e,&list[i].q);
> 		list[i].id=i;
> 	}
> 	qsort(list+1,m,sizeof(ques),cmp);
> 	for(int j=list[1].s;j<=list[1].e;j++)
> 		refer.insert(num[j]);
> 
> 	list[1].ans=refer.get_rank(list[1].q);
> 	for(int i=2;i<=m;i++)
> 	{
> 		if(list[i].s>=list[i-1].e)//区间错开
> 		{
> 			for(int j=list[i-1].s;j<=list[i-1].e;j++)
> 				refer.erase(num[j]);
> 			for(int j=list[i].s;j<=list[i].e;j++)
> 				refer.insert(num[j]);
> 		}
> 		else if(list[i].s<=list[i-1].e&&list[i].e>list[i-1].e)//区间部分包含
> 		{
> 			for(int j=list[i-1].e+1;j<=list[i].e;j++)
> 				refer.insert(num[j]);
> 			for(int j=list[i-1].s;j<list[i].s;j++)
> 				refer.erase(num[j]);
> 		}
> 		else //子集
> 		{
> 			for(int j=list[i-1].s;j<list[i].s;j++)
> 				refer.erase(num[j]);
> 			for(int j=list[i].e+1;j<=list[i-1].e;j++)
> 				refer.erase(num[j]);
> 		}
> 		list[i].ans=refer.get_rank(list[i].q);
> 	}
> 	qsort(list+1,m,sizeof(ques),cmp1);
> 	for(int i=1;i<=m;i++)
> 		printf("%d\n",list[i].ans);
> 	return 0;
> 
> 
> }
>

Home Page Go Back To top