首先用平衡樹(shù)做出來(lái)了
學(xué)了一下傳說(shuō)中SBT，比較好用，編碼不是很難
能夠?qū)懚娌檎覙?shù)就會(huì)寫(xiě)一半了。
平衡樹(shù)只維護(hù)當(dāng)前的區(qū)間，然后查找當(dāng)前區(qū)間的
第K元素。
所以首先把區(qū)間從小到大排序，這樣可以保證每個(gè)
元素只插入一次，刪除也只有一次。
如樣例。 首先把 1-5 區(qū)間元素插入，
到第二個(gè)區(qū)間 2-7 時(shí)，把 1-2 刪除， 5-7 插入
SBT插入和刪除都是logn,總復(fù)雜度nlogn+ mlogm
代碼
#include <iostream>
using namespace std;
typedef int Type;
struct SBNode{
int size;
Type key;
SBNode* lchild, *rchild;
SBNode(){}
SBNode( SBNode*l, SBNode*r, int s, Type k ):
lchild(l), rchild(r), size(s), key(k) {}
};
class SBTree{
private:
SBNode* root;
SBNode* _null;
void left_rotate ( SBNode*& root );
void right_rotate( SBNode*& root );
void maintain( SBNode*& root, bool style );
void insert( SBNode*& root, Type key );
void erase ( SBNode*& root, Type key );
void clear ( SBNode* root );
public:
SBTree ();
~SBTree();
void insert( Type key ); // 插入元素
void erase ( Type key ); // 刪除元素
Type get_rank( int k ); // 獲得第 k 個(gè)元素
void clear(); // 清空
};
Type SBTree::get_rank( int k ){
SBNode* tmp= root;
for( ;; ){
if( tmp->lchild->size> k ) tmp= tmp->lchild;
else if( k> tmp->lchild->size ){
k-= tmp->lchild->size+ 1;
tmp= tmp->rchild; }
else break;}
return tmp->key;
}
void SBTree::clear( SBNode* root ){
if( root!= _null ){
clear( root->lchild );
clear( root->rchild );
delete root; }
}
void SBTree::clear(){
clear(root); delete _null; }
void SBTree::erase( Type key ){
erase( root, key ); }
void SBTree::erase( SBNode*& root, Type key ){
if( root== _null ) return; root->size--;
if( root->key== key ){
SBNode* 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 );
}
void SBTree::insert( SBNode*& root, Type key ){
if( root== _null ){
root= new SBNode( _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 );
}
void SBTree::insert( Type key ){
insert( root, key ); }
SBTree::SBTree(){
_null= new SBNode();
root= _null;
root->lchild= root->rchild= _null;
root->size= 0;
}
SBTree::~SBTree(){
clear();
}
void SBTree::left_rotate( SBNode*& root ){
SBNode* 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;
}
void SBTree::right_rotate( SBNode*& root ){
SBNode* 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;
}
void SBTree::maintain( SBNode*& 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);
}
#define N 100011
struct Node{
int x, y, k, pos;
};
int n, m;
int d[N], ans[N];
Node q[N];
int cmp( const void* a, const void* b ){
Node* ta= (Node*)a;
Node* tb= (Node*)b;
if( ta->x== tb->x ) return ta->y- tb->y;
return ta->x- tb->x;
}
SBTree test;
int main()
{
scanf("%d%d",&n,&m );
for( int i= 1; i<= n; ++i )
scanf("%d", d+ i );
for( int i= 0; i< m; ++i )
{
scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].k );
q[i].pos= i; }
qsort( q, m, sizeof(q[0]), cmp );
for( int i= q[0].x; i<= q[0].y; ++i )
test.insert( d[i] );
ans[ q[0].pos ]= test.get_rank( q[0].k- 1 );
for( int i= 1; i< m; ++i ){
if( q[i].x< q[i-1].y ){
for( int j= q[i-1].x; j< q[i].x; ++j )
test.erase( d[j] );
for( int j= q[i-1].y+ 1; j<= q[i].y; ++j )
test.insert( d[j] ); }
else {
for( int j= q[i-1].x; j<= q[i-1].y; ++j )
test.erase( d[j] );
for( int j= q[i].x; j<= q[i].y; ++j )
test.insert( d[j] );
}
ans[ q[i].pos ]= test.get_rank( q[i].k- 1 );
}
for( int i= 0; i< m; ++i ) printf("%d\n", ans[i] );
return 0;
}
另外還用數(shù)狀數(shù)組做了下
樹(shù)狀數(shù)組的做法和以上相似，只是首先要把離散化一
下， 稍微有些麻煩。插入相當(dāng)于在樹(shù)狀數(shù)據(jù)對(duì)應(yīng)元素
增加 1， 刪除相當(dāng)于增加 －1， 查找每 k 元素，相
當(dāng)于找到 sum 等于 k的最小元素，這個(gè)可以二分sum
去求， 總復(fù)雜度為 mlogm+ nlognlogn。
不過(guò)好像求第k元素有一個(gè) nlogn 的做法， 沒(méi)學(xué)會(huì)
還得去看看。
代碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define lowbit(x) ( (x)&(-(x)) )
#define MAXN 100010
struct FNode{ int data, index; };
struct SNode{ int x, y, k, idx; };
int count[MAXN], ans[MAXN], inp[MAXN], pos[MAXN];
int n, m;
FNode d[MAXN];
SNode q[MAXN];
void init(){
memset( count, 0, sizeof(count) );
}
void update( int pos, int value ){
while( pos<= n ){
count[pos]+= value;
pos+= lowbit(pos); }
}
int sum( int pos ){
int s= 0;
while( pos ){
s+= count[pos];
pos-= lowbit(pos);
}
return s;
}
int cmpa( const void* a, const void* b ){
FNode* ta= (FNode*)a, *tb= (FNode*)b;
return ta->data- tb->data; }
int cmpb( const void* a, const void* b ){
SNode* ta= (SNode*)a, *tb= (SNode*)b;
if( ta->x== tb->x ) return ta->y- tb->y;
return ta->x- tb->x;
}
int bfind( int k ){
int left= 1, right= n+ 1, mdl;
while( left+ 1< right ){
mdl= ( left+ right )>> 1;
if( sum(mdl)>= k ) right= mdl;
else left = mdl;
}
if( sum(left)== k ) return left;
return left+ 1;
}
int main(){
init();
scanf("%d%d",&n, &m );
for( int i= 1; i<= n; ++i ) {
scanf("%d", &d[i].data );
inp[i]= d[i].data;
d[i].index= i; }
qsort( d+ 1, n, sizeof(d[0]), cmpa );
for( int i= 1; i<= n; ++i ) pos[ d[i].index ]= i;
for( int i= 0; i< m; ++i ){
scanf("%d%d%d",&q[i].x, &q[i].y, &q[i].k );
q[i].idx= i; }
qsort( q, m, sizeof(q[0]), cmpb );
for( int i= q[0].x; i<= q[0].y; ++i )
update( pos[i], 1 );
ans[ q[0].idx ]= inp[ d[ bfind( q[0].k ) ].index ];
for( int i= 1; i< m; ++i ){
if( q[i].x< q[i-1].y ){
for( int j= q[i-1].x; j< q[i].x; ++j )
update( pos[j], -1 );
for( int j= q[i-1].y+ 1; j<= q[i].y; ++j )
update( pos[j], 1 );
}
else {
for( int j= q[i-1].x; j<= q[i-1].y; ++j )
update( pos[j], -1 );
for( int j= q[i].x; j<= q[i].y; ++j )
update( pos[j], 1 );
}
ans[ q[i].idx ]= inp[ d[ bfind( q[i].k ) ].index ];
}
for( int i= 0; i< m; ++i ) printf("%d\n", ans[i] );
return 0;
}
這題還可以用其它數(shù)據(jù)結(jié)構(gòu)做出
確實(shí)是一道練習(xí)數(shù)據(jù)結(jié)構(gòu)的好題啊
posted on 2009-04-12 18:38
Darren 閱讀(373)
評(píng)論(0) 編輯 收藏 引用