划分树学习小记 Poj 2104+Poj 2761+Hdu 2665 (区间第k大数)

做某线段树专题，结果第一题就不会。。。。囧

网上有各种代码实现最后挑了一个和我代码风格比较像的学习了下，发现这东西实现过程中有好多细节需要注意。

从以下地方学习，并参考了部分代码：

poj 2104 K-th Number(划分树) - 志当存高远 - 博客频道 - CSDN.NET
http://blog.csdn.net/fp_hzq/article/details/7993364

划分树学习（poj 2104，hdu 3473） - 小媛在努力~ - 博客频道 - CSDN.NET
http://blog.csdn.net/zxy_snow/article/details/6681086

划分树 - - 博客频道 - CSDN.NET
http://blog.csdn.net/shiqi_614/article/details/8041390

三道题代码基本一样……

没有理解 Poj2761 题目描述的最后一句Hence any feeding inteval will not contain another completely,though the intervals may intersect with each other.?

的作用在那里……希望路过的大家指导一下。

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

const int N=100010;

int data[N],parti[22][N],divide[22][N];

void Build (int left,int right,int d)
{
	if (left==right)
		return;
	int i,t1,t2,same=0;    //same用来计数和中间值data[mid]相等的,且分到左孩子的数的个数
	int mid=(left+right)>>1;
	for (i=left;i<=right;i++)
		same+=(parti[d][i]<data[mid]);
	same=mid-left+1-same;     //mid-left+1表示左侧共有多少个数
                              //最后求出左侧有多少与排序后相等的数
	for (t1=i=left,t2=mid+1;i<=right;i++)
		if (parti[d][i]==data[mid] && same) //左侧还有足够空间放相等的数
			--same,parti[d+1][t1++]=parti[d][i],divide[d][i]=1;
		else if (parti[d][i]<data[mid])     //分到左侧
			parti[d+1][t1++]=parti[d][i],divide[d][i]=1;
		else                            //分到右侧
			parti[d+1][t2++]=parti[d][i],divide[d][i]=0;
	for (i=left;i<right;i++) //divide[d][i]表示在该区间i之前(包括i),有多少个被划进左区间
		divide[d][i+1]+=divide[d][i];
	Build (left,mid,d+1);
	Build (mid+1,right,d+1);
}

int Query (int target_L,int target_R,int k,int left,int d)
{
	if (left==right)
		return parti[d][left];
	int mid=(left+right)>>1,w1=0,w2=divide[d][target_R];
	if (target_L>left)//w1表示区间[left,target_L)有多少个小于等于data[mid]的数被分到左边
		//w2表示区间[target_L,target_R]有多少个小于等于data[mid]的数被分到左边
		w2-=(w1=divide[d][target_L-1]);
	if (w2>=k)  //如果划分到左边的多于k,则查询左边
		return Query (left+w1,left+w1+w2-1,k,left,d+1);

	k-=w2;
	w1=target_L-left-w1; //w1表示区间[left,target_L)有多少个被分到右边
	w2=target_R-target_L+1-w2; //w2表示区间[target_L,target_R]有多少个被分到右边
	return Query (mid+w1+1,mid+w1+w2,mid+1,d+1);
}

int main ()  //Poj 2104+2761
{
	int n,m;
	while (~scanf("%d%d",&n,&m))
	{
		for (int i=1;i<=n;i++)
		{
			scanf("%d",&data[i]);
			parti[0][i]=data[i];
		}
		sort(data+1,data+n+1);
		Build (1,n,0);
		int a,b,k;
		while (m--)
		{
			scanf("%d%d%d",&a,&b,&k);
			printf("%dn",Query(a,1,0));
		}
	}
	return 0;
}

/*
int main ()   //Hdu 2665数据较强
{
	int T,m;
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d",&m);
		for (int i=1;i<=n;i++)
		{
			scanf("%d",0));
		}
	}
	return 0;
}*/