POJ3368_Frequent Values_solution

发布时间:2017-2-27 3:22:40 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ3368_Frequent Values_solution",主要涉及到POJ3368_Frequent Values_solution方面的内容,对于POJ3368_Frequent Values_solution感兴趣的同学可以参考一下。

Frequent values Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 11727   Accepted: 4285 Description You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj. Input The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query. The last test case is followed by a line containing a single 0. Output For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range. Sample Input 10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0 Sample Output 1 4 3 Source Ulm Local 2007 题目的意思很好理解,找一个区间出现频率最大的数的出现次数。除了使用线段树,还真的想不出其他更好的办法来处理。这道题目相比POJ3667_hotel又简单了点,因为这道题目只有查询,没有更新,所以,在了解POJ3667解法的情况下,再来看这道题目就非常容易解决了。 在线段树的节点定义三个信息域,max_len表示该区间段的最大频率,start_left_len表示该区间段最左段一串相同数字的频率,end_right_len表示该区间段最右段一串相同数字的频率。 (1)建树buildTree()过程如下: 对于叶子节点肯定有: max_len=start_left_end_right_len=1; 当回溯的时候,我们这样更新父节点的信息: 父节点的start_left_len=左孩子的start_left_len; 父节点的end_right_len=右孩子的end_right_len; 父节点的max_len=getMax(左孩子的max_len,有孩子的max_len); 接下来很重要的一步,就是如何将左孩子和右孩子的信息融合? 如果arr[mid]==arr[mid+1],arr[]存放的是原数组的元素,因为只有在arr[mid]==arr[mid+1]的时候左孩子和右孩子才有联系,否则可以看成两颗不相关树。                   这时需要更新的信息有:max_len=getMax(max_len,leftChild.end_right_len+rightChild.start_left_len);                    如果左孩子管理的数组区间只有一个数,即leftChild.start_left_len==mid-left+1                                                    那么父节点的start_left_len+=rightChild.start_left_len;//即和右孩子最左段的信息融合                    如果右孩子管理的数组区间只有一个数,即rightChild.end_right_len=right-mid                                                     那么父节点的end_right_len+=leftChild.end_right_len;//即与左孩子的最右段的信息融合 (2)查询query(l,r) 查询的时候需要注意的地方,设查询区间为[l,r],如果[l,r]跨左右子节点:       如果arr[mid] != a rr[mid+1]                返回getMax(query(l,mid),query(mid+1,r));       如果arr[mid]==arr[mid+1]                中间段相连的信息这么取,设leftMin是mid左边的有效长度,rightMin是mid+1右边的有效长度,那么                leftMin=getMin(mid-l+1,leftChild.end_right_len);//总是取较小的那段,自己可以画图感受一下,下同                rightMin=getMin(r-mid,rightChild.start_left_len);                用queryMax记录左右子树查询结果,queryMax=getMax(query(l,mid),query(mid+1,r));                返回结果为:getMax(leftMin+rightMin,queryMax); 贴上源码: #include<stdio.h> #define lson pos<<1 #define rson pos<<1|1 #define MAXN 100005 int n,q,arr[MAXN]; struct segTreeInfo { int left,right; int max_len,start_left_len,end_right_len; }; segTreeInfo segTree[MAXN*3]; int getMax(int a,int b) { return a>b?a:b; } int getMin(int a,int b) { return a<b?a:b; } void buildTree(int pos,int left,int right)//建立线段树 { int mid=(left+right)/2; segTree[pos].left=left; segTree[pos].right=right; if(left==right) { segTree[pos].start_left_len=1; segTree[pos].end_right_len=1; segTree[pos].max_len=1; return; } buildTree(lson,left,mid); buildTree(rson,mid+1,right); //父节点的信息域都需要子树建成后回溯来得到 segTree[pos].start_left_len=segTree[lson].start_left_len; segTree[pos].end_right_len=segTree[rson].end_right_len; segTree[pos].max_len=getMax(segTree[lson].max_len,segTree[rson].max_len); if(arr[mid]==arr[mid+1])//如果左右子树的中间段是相同的数字,那么需要将中间的信息融合 { segTree[pos].max_len=getMax(segTree[pos].max_len,segTree[lson].end_right_len+segTree[rson].start_left_len); if(segTree[lson].start_left_len==mid-left+1) segTree[pos].start_left_len+=segTree[rson].start_left_len; if(segTree[rson].end_right_len==right-mid) segTree[pos].end_right_len+=segTree[lson].end_right_len; } } int query(int pos,int l,int r) { int left=segTree[pos].left,right=segTree[pos].right; if(l<=left&&r>=right)//完全覆盖该段区域 { return segTree[pos].max_len; } int mid=(left+right)/2; if(r<=mid)//落在左子树 return query(lson,l,r); else if(l>mid)//落在右子树 return query(rson,l,r); else if(arr[mid]!=arr[mid+1])//接下来两个else是处理跨左右子树的 return getMax(query(lson,l,mid),query(rson,mid+1,r));//如果左右子树相接的地方元素不一样,只要在分别取查询左右子树再返回较大值就可以了 else//这是处理arr[mid]==arr[mid+1] { int leftMin=getMin(mid-l+1,segTree[lson].end_right_len);//中间段在左子树的有效长度 int rightMin=getMin(r-mid,segTree[rson].start_left_len);//中间段在右子树的有效长度 return getMax(leftMin+rightMin,getMax(query(lson,l,mid),query(rson,mid+1,r)));//中间段与左子树获得的最大值、右子树获得的最大值比较取最大值就是结果 } } int main() { int i,left,right; while(1) { scanf("%d",&n); if(0==n)break; scanf("%d",&q); for(i=1;i<=n;i++) scanf("%d",&arr[i]); buildTree(1,1,n); for(i=1;i<=q;i++) { scanf("%d%d",&left,&right); printf("%d\n",query(1,left,right)); } } }

上一篇:POJ 1450 最短距离
下一篇:C++时间函数

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。