学步园

题意 : 给出N个形式为s/n的(字符串/数字)对，要求建立一颗Treap

思路 : 分治+RMQ(Range maximum Query) ，其中RMQ可以用线段树实现，也可以用Sparse Table实现。

线段树的实现很简单，自己画画就出来了。

Sparse Table的实现倒是比较巧妙，其中用到了与多重背包问题相似的二进制思想。

该思想的主要内容是，任何一个正整数都可以被拆成2的i次方之和( i >= 0 )。

例如:13 = 8 + 4 + 1

          7 = 4 + 2 + 1

证明略.

这题的两种实现

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 50000;

// 对象
int N;
struct Node {
	char s[100];
	int n;
}A[Max];

// 函数
//----------------------- Sparse Table操作 ------------------------//
int M[Max][16]; // 2 ^ 16 >= Max
void Build_ST()
{
	memset( M, -1, sizeof(M) );
	// initialize M for the intervals with 1
	for( int i = 0; i < N; ++ i ) M[i][0] = i;
	// compute values from smaller to bigger intervals
	for( int j = 1; ( 1 << j ) <= N; ++ j )
		for( int i = 0; i + ( 1 << j ) <= N; ++ i )
			if( A[ M[i][j-1] ].n > A[ M[i+(1<<(j-1))][j-1] ].n )
				M[i][j] = M[i][j-1];
			else 
				M[i][j] = M[i+(1<<(j-1))][j-1];
}
/*
*  function : query the index of the max value in array A[b,e]
*/
int Query( const int b, const int e )
{
	int i = 0; // 2 ^ i:the length of the segment
	while( b + ( 1 << i ) - 1 < e ) 
		++ i;

	if( b + ( 1 << i ) - 1 == e ) return M[b][i];
	else {
		int ind = Query( b + (1 << (i-1)), e );
		if( A[ M[b][i-1] ].n >= A[ ind ].n ) return M[b][i-1];
		else return ind;
	}
}
//--------------------------- end -----------------------------//
bool greater( const Node & n1, const Node & n2 )
{
	return strcmp( n1.s, n2.s ) <= 0;
}
void Dq( const int b, const int e )
{
	if( b > e ) return;
	int ind = Query( b, e );
	printf( "(" );
	Dq( b, ind - 1 ), printf( "%s/%d", A[ind].s, A[ind].n ), Dq( ind + 1, e );
	printf( ")" );
}

int main()
{
	freopen( "1.txt", "r", stdin );
	while( scanf( "%d", & N ) && N != 0 ) {
		for( int i = 0; i < N; ++ i ) {
			getchar();
			cin.getline( A[i].s, 100, '/' );
			scanf( "%d", & A[i].n );
		}

		sort( A, A + N, greater );

		Build_ST();
		Dq( 0, N - 1 );
		printf( "\n" );
	}
	system( "pause" );
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

const int Max = 50000;

// 对象
int N;
struct Node {
	char s[100];
	int n;
}A[Max];
struct TreeNode {
	int l, r;
	int ind; // 区间[l,r]最大值的下标
}t[Max*4];

// 函数
//----------------------- 线段树操作 ------------------------//
int Build( const int l, const int r, const int id )
{
	t[id].l = l, t[id].r = r;
	if( l == r ) { // 叶子节点
		t[id].ind = l;
		return t[id].ind;
	}

	// 非叶子节点
	int mid = ( l + r ) >> 1;
	int p = Build( l, mid, id * 2 ); // p:左子树最大值索引
	int q = Build( mid + 1, r, id * 2 + 1 ); // q:右子树最大值索引
	if( A[p].n >= A[q].n ) 
		t[id].ind = p;
	else 
		t[id].ind = q;
	return t[id].ind; // 返回区间[l,r]最大值索引
}
int Query( const int b, const int e, const int id )
{
	if( b == t[id].l && e == t[id].r )
		return t[id].ind;

	int mid = ( t[id].l +t[id]. r ) >> 1;
	if( e <= mid )
		return Query( b, e, id * 2 );
	else if( b > mid )
		return Query( b, e, id * 2 + 1 );
	else {
		int p = Query( b, mid, id * 2 );
		int q = Query( mid + 1, e, id * 2 + 1 );
		if( A[p].n >= A[q].n ) return p;
		else return q;
	}
}
//--------------------------- end -----------------------------//
bool greater( const Node & n1, const Node & n2 )
{
	return strcmp( n1.s, n2.s ) <= 0;
}
void Dq( const int b, const int e )
{
	if( b > e ) return;
	int ind = Query( b, e, 1 );
	printf( "(" );
	Dq( b, ind - 1 ), printf( "%s/%d", A[ind].s, A[ind].n ), Dq( ind + 1, e );
	printf( ")" );
}

int main()
{
	freopen( "1.txt", "r", stdin );
	while( scanf( "%d", & N ) && N != 0 ) {
		for( int i = 0; i < N; ++ i ) {
			getchar();
			cin.getline( A[i].s, 100, '/' );
			scanf( "%d", & A[i].n );
		}

		sort( A, A + N, greater );

		Build( 0, N - 1, 1 );
		Dq( 0, N - 1 );
		printf( "\n" );
	}
	system( "pause" );
	return 0;
}

不明白线段树对于区间模型这么好用，为啥不叫区间树，叫线段树真是掩盖了这种数据结构的光芒啊。

以后我就叫它区间树了。