首页 > 代码库 > hdu 4417 划分树(模版)
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 划分树(模版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。