Binary Index Tree And Segment Tree for PKU #3378 Crazy Thairs

现在的位置: 首页 > 综合 > 正文

Binary Index Tree And Segment Tree for PKU #3378 Crazy Thairs

2013年10月07日 ⁄ 综合 ⁄ 共 4788字 ⁄ 字号小中大 ⁄ 评论关闭

Crazy Thairs

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 3111		Accepted: 699

Description

These days, Sempr is crazed on one problem named Crazy Thair. Given N (1 ≤ N ≤ 50000) numbers, which are no more than 10⁹, Crazy Thair is a group of 5 numbers {i, j, k, l, m} satisfying:

1. 1 ≤ i < j < k < l < m ≤ N
2. A_i < A_j < A_k < A_l < A_m

For
example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy
Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2,
3, 4, 5, 7}.

Could you help Sempr to count how many Crazy Thairs in the sequence?

Input

Input contains several test cases. Each test case begins with a line containing a number N, followed by a line containing N numbers.

Output

Output the amount of Crazy Thairs in each sequence.

Sample Input

5
1 2 3 4 5
7
2 1 3 4 5 7 6
7
1 2 3 4 5 6 7

Sample Output

1
4
21

Source

POJ Monthly--2007.09.09, tdzl2003

最近正看到线段树,碰到上面的这个题目,正好有个施展的机会.

分析:

如果要知道连续5个递增数的个数,我们从2个开始窥探,继而扩展到3个,4个最后5个.如果我们把这些数据用表来表示的话,就会得到这样的一张表:(我们选取2 1 3 4 5 7 6作为例子)

number: 2 1 3 4 5 7 6

1: 1 1 1 1 1 1 1

2: 0 0 2 3 4 5 5

3: 0 0 0 2 5 9 9

4: 0 0 0 0 2 7 7

5: 0 0 0 0 0 2 2

所以得到Crazy Thairs的个数是5个.从这里可以发现规律如下F(i, k) = ∑F(i-1,k-1),就是说对于某一位K而言,连续i个递增数据的个数是之前k-1位连续i-1个递增数据的和.所以很容易联想到线段数是个很好的主意.我们把每次的插入数据带有一定的权,就完全可以适用于这个情形.

这里的思路就是

1. 首先nlogn的排序任选一种.(同时得到每个数字的相对于排序完成后的位置信息(idx))

2. 每个对一个idx数组插入到线段数,得到一组新的值.循环的插入线段数.(完成从1-2, 2-3, 3-4, 4-5)的操作

3. 累加5的个数,注意大数(大于int64)

//注,这里的代码不是完全的代码:

// if find, return the index, else return -1; 
int binraySearch(int a[], int length, int v) 
{ 
	int l = 0; 
	int r = length - 1; 
	int mid = 0; 
	bool find = false; 
	while (l<=r) 
	{ 
		mid = (l+r)>>1; 
		if (a[mid] < v) 
		{ 
			l = mid+1; 
		} 
		else if (a[mid] > v) 
		{ 
			r = mid - 1; 
		} 
		else 
		{ 
			//find; 
			find = true; 
			break; 
		} 
	} 
	if (find) 
		return mid; 
	else 
		return -1; 
} 
#define ARRAY_LENGTH 50000 
void calBySegmentTree(int* pIdx, long long * ps, long long* pd, int n) 
{ 
	long long* pt = new long long[(n+1)*4]; 
	memset(pt, 0, sizeof(long long)*(n+1)*4); 
	for (int i=0;i<n;i++) 
	{ 
		int l = 0; 
		int r = n-1; 
		int n = 1; 
		long long s = 0; 
		int v = pIdx[i]; 
		while (l<r) 
		{ 
			int mid = (l+r) >> 1; 
			if ( v > mid ) 
			{ 
				// plus current tree node value, means all left nodes are counted 
				s += pt[n]; 
				l = mid + 1; 
				// right child node, n = 2*n+1; 
				n = (n << 1); 
				n ++ ; 
			} 
			else 
			{ 
				// left child node 
				r = mid; 
				pt[n] += ps[i] ; 
				n = (n << 1); 
			} 
		} 
		s += pt[n]; 
		pd[i] = s; 
		pt[n] += ps[i]; 
	} 
	delete[] pt; 
} 
bool calculate(int* pArray, int n, int groupLength/*Crazy Thair is a group of 5 numbers, so here it's 5*/) 
{ 
	int* pb = new int[n]; 
	memcpy_s(pb, n*sizeof(int), pArray, sizeof(int)*n); 
	MyLib::mergeSort(pArray, n); 
	long long * ps = new long long [n]; 
	long long * pd = new long long [n];
	int* pIdx = new int[n]; 
	for (int i=0;i<n;i++) 
	{ 
		ps[i] = 1; 
		pd[i] = 0; 
		pIdx[i] = binraySearch(pArray, n, pb[i]); 
	} 
	for (int i=0;i<groupLength-1;i++) 
	{ 
		calBySegmentTree(pIdx, ps,pd, n); 
		long long * pTemp = ps; 
		ps = pd; 
		pd = pTemp; 
		memset(pd, 0, sizeof(long long)*n); 
	}
	long long ans1 = 0,ans2 = 0; 
	for( int i = 0 ; i < n ; i++ ) 
	{ 
		ans1 += (ans2+ps[i])/10000000000000000LL; 
		ans2 = (ans2+ps[i])%10000000000000000LL; 
	} 
	if(ans1) 
	{ 
		std::cout<<ans1; 
		std::cout<<ans2<<std::endl; 
	} 
	else 
		std::cout<<ans2<<std::endl; 
	return true; 
}

从个人情感的角度讲是个可以用的解决方案,但是问题在于线段数带来的种种

long long* pTree = new long long[(nLength+1)*4]; 的开销也是很刺眼的.(大家都知道这里的线段数的大小是2 * 2^{[logN] + 1})要是要解决掉这种开销.我们可以用更为实际的BIT(Binary Index Tree)来取代.这里的BIT的定义可以到

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

找到定义.我们具体的方案就是:

#define ARRAY_LENGTH 50000 
bool calculateBIT(int* pArray, int n, int groupLength/*Crazy Thair is a group of 5 numbers, so here it's 5*/) 
{ 
	int* pb = new int[n]; 
	memcpy_s(pb, n*sizeof(int), pArray, sizeof(int)*n); 
	MyLib::mergeSort(pArray, n); 
	long long * ps = new long long [n]; 
	long long * pd = new long long [n]; 
	int* pIdx = new int[n]; 
	for (int i=0;i<n;i++) 
	{ 
		ps[i] = 1; 
		pd[i] = 0; 
		pIdx[i] = binraySearch(pArray, n, pb[i]); 
	} 
	MyLib::BinaryIndexTree<long long, ARRAY_LENGTH> bit;
	for (int i=0;i<groupLength-1;i++) 
	{ 
		for (int i=0;i<n;i++) 
		{ 
			pd[i] = bit.read(pIdx[i]); 
			bit.update(pIdx[i], ps[i]); 
		} 
		bit.clear(); 
		{ 
			//exchange a and r; 
			long long * pTemp = ps; 
			ps = pd; 
			pd = pTemp; 
			memset(pd, 0, sizeof(long long)*n); 
		} 
	}
	long long ans1 = 0,ans2 = 0; 
	for( int i = 0 ; i < n ; i++ ) 
	{ 
		ans1 += (ans2+ps[i])/10000000000000000LL; 
		ans2 = (ans2+ps[i])%10000000000000000LL; 
	} 
	if(ans1) 
	{ 
		std::cout<<ans1; 
		std::cout<<ans2<<std::endl; 
	} 
	else 
		std::cout<<ans2<<std::endl;
	return true; 
}

把原来的函数换一个新的,然后再来一个BIT的模板,目前只是实现了够用的read和update函数,下面是这个模板的定义:

#pragma once 
namespace MyLib 
{ 
	template <class T, int maxVal> class BinaryIndexTree 
	{
	public: 
		BinaryIndexTree(); 
		~BinaryIndexTree(); 
		// the real idx could start from 0-max. 
		// here we have to transfer to 1-max+1 for calculation 
		void update(int idx, T val); // update the t(tree) array 
		T read(int idx);			 // read the 
		void clear(); 
	private: 
		T* t; 
	}; 
	template<class T, int maxVal> BinaryIndexTree<T, maxVal>::BinaryIndexTree() 
	{ 
		t = new T[maxVal+1]; 
		memset(t, 0, (maxVal+1)*sizeof(T)); 
	} 
	template<class T, int maxVal> BinaryIndexTree<T, maxVal>::~BinaryIndexTree() 
	{ 
		delete[] t; 
	} 
	template<class T, int maxVal> void BinaryIndexTree<T, maxVal>::update(int idx, T val) 
	{ 
		idx++; 
		while (idx <= maxVal+1){ 
			t[idx] += val; 
			idx += (idx & -idx); 
		} 
	}
	template<class T, int maxVal> T BinaryIndexTree<T, maxVal>::read(int idx) 
	{ 
		idx++; 
		T sum = 0; 
		while (idx > 0){ 
			sum += t[idx]; 
			idx -= (idx & -idx); 
		} 
		return sum; 
	} 
	template<class T, int maxVal> void BinaryIndexTree<T, maxVal>::clear() 
	{ 
		memset(t, 0, (maxVal+1)*sizeof(T)); 
	} 
};

需要注意的一点就是idx的值的范围,我非常倾向于这里从1开始到max+1,而不是0-max等等...外部的调用一般都是0-max的范围,所以特地在这里++了一下.这里用模板是考虑到是否会有更通用的情形以后可以扩展.但是写好了看看好像没有:( 不管了好歹可以工作,而且比线段数更高效!用的空间更少.

附:做这种题目纯粹为了消遣:)随便玩玩,自己水平还很不行

【上篇】Ubuntu 6.10硬盘安装手记
【下篇】ubuntu 11.10 x64编译安装bochs2.5.1

作者: huangjin1011

该日志由 huangjin1011 于11年前发表在综合分类下，最后更新于 2013年10月07日.
转载请注明: Binary Index Tree And Segment Tree for PKU #3378 Crazy Thairs | 学步园 +复制链接

抱歉!评论已关闭.

学步园

Binary Index Tree And Segment Tree for PKU #3378 Crazy Thairs

作者: huangjin1011

书签

最新文章New

本站推荐

返回首页