hdu 4417 划分树（模版）

这次是彻底把划分树搞明白了，与此同时发现了模版的重要性。写程序一个字符都不能错啊~~~

划分树详解：点击打开链接

题意：求一组数列中任意区间不大于h的个数。

这个题的做法是用二分查询  求给定区间内的中值再与K进行比较。

重点介绍划分树：

数据结构：

t[20][maxn] // 树结构，划分树存储

sum[20][maxn] // 记录该行[l,i] 中i到l有多少个存在左子树中

as[maxn]  //原始数组排序后结果

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <bitset>
#include <iostream>
#include <algorithm>  
#define inf 0x3fffffff
#define mid ((l+r)>>1)
const int maxn=100000+100;
typedef unsigned __int64 ull;
using namespace std;
int N,M;

int t[30][maxn]; // 树结构，划分树存储
int sum[30][maxn]; // 记录该行[l,i] 中i到l有多少个存在左子树中
int as[maxn];//排序后数组

//建树是依据上一层建立下一层，所以t[p+1][ls++]=t[p][i]; l==r判断的条件放在循环后是为了让每个元素都到最底层
void build(int p,int l,int r)
{
	int ls=l,rs=mid+1;
	int lm=0,i;
	for(i=rs-1;i>=l;i--)// ls rs 左右子树开始的位置 lm 放入左子树的中值数目（避免中值过多树不平衡）
		if(as[i]==as[mid]) lm++;
		else break;
	for(i=l;i<=r;i++)
	{
		if(i==l) sum[p][i]=0;//sum的计算若为初始则为0，注意这里的每行sum有多个分开的树
		else     sum[p][i]=sum[p][i-1];
		if(t[p][i]==as[mid])
			if(lm) //将部分中值的数放入左边
				lm--,sum[p][i]++,t[p+1][ls++]=t[p][i];
			else t[p+1][rs++]=t[p][i];
		else if(t[p][i]<as[mid]) sum[p][i]++,t[p+1][ls++]=t[p][i];//小于中值放入左边
		else t[p+1][rs++]=t[p][i];//大于放入右边，sum与其无关
	}
	if(l==r) return;
	build(p+1,l,mid);
	build(p+1,mid+1,r);

}
/*
在p层，[l,r]范围内查询[ql,qr]中第K大数
l+s  跳过查询区间前放入左子树个数，l+sum[p][qr]-1  [l,qr]放入左子树的个数
ql-l-s 查询区间前放入右子树的个数，qr-l-sum[p][qr] [l,qr]放入右子树的个数
*/
int query(int p,int l,int r,int ql,int qr,int k)
{
	if(l==r) return t[p][l];
	int s,ss;//s是ql左边有多少放入下层左子树，ss是[ql,qr]中有多少放入下层左子树
	if(ql==l)
		s=0,ss=sum[p][qr];
	else
		s=sum[p][ql-1],ss=sum[p][qr]-s;
	if(k<=ss)
		return query(p+1,l,mid,l+s,l+sum[p][qr]-1,k);
	else
		return query(p+1,mid+1,r,mid+1+ ql-l-s,mid+1 +qr-l-sum[p][qr],k-ss);
}



int main()
{
    int T;
    int n,m,cas=1;
	int i,l,r,k;
    scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&N,&M);
		for(i=0;i<N;i++)
			scanf("%d",as+i),t[0][i]=as[i];
		sort(as,as+N);
		build(0,0,N-1);
		printf("Case %d:\n",cas++);
		for(i=0;i<M;i++)
		{
			scanf("%d%d%d",&l,&r,&k);
			int mi=1,ma=r-l+1,Mid,ans=r-l+2; 
			while(mi<=ma)  
            {  
                Mid=(mi+ma)>>1;  
                int tmp=query(0,0,N-1,l,r,Mid);
                if(tmp>k)  
                {  
                    ans=Mid;  
                    ma=Mid-1;  
                }  
                else  
                mi=Mid+1;  
            }  
			printf("%d\n",ans-1);
		}


	}
    return 0;
}

hdu 4417 划分树（模版）

原文：http://blog.csdn.net/gg_gogoing/article/details/40209033