设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

POJ 3368 Frequent values

2014-03-25 14:46:00.0 2014POJ 线段树 POJ 刷题 线段树  
导读:RMQ问题第二题,还是用线段树写的,DP很渣ST算法看不懂啊~~题目大意:给出依次不下降的n个数,求某个区间内出现次数最多的数字的个数。解题思路:这题用线段树写的话如果想不出来就卡死,想出来了真的很简单~~对于每一个区间来说,会有中间的整个的数块,和两端的小数块。中间的用线段树查询就行,两边的用二分来查找。代码中有注释。下面是代码:#include #include const int Max=1...。。。

RMQ问题第二题,还是用线段树写的,DP很渣ST算法看不懂啊~~


题目大意:

给出依次不下降的n个数,求某个区间内出现次数最多的数字的个数。


解题思路:

这题用线段树写的话如果想不出来就卡死,想出来了真的很简单~~

对于每一个区间来说,会有中间的整个的数块,和两端的小数块。中间的用线段树查询就行,两边的用二分来查找。代码中有注释。


下面是代码:

#include #include const int Max=100005;int n,q;int num[Max],sum[Max],node[Max<<2];int max(int a,int b){    if(a>1;    Build(l,m,tr<<1);    Build(m+1,r,tr<<1|1);    PushUp(tr);}int  Findnum(int key ,int l,int r){    int m;    while(l<=r)    {        m=(l+r)>>1;        if(sum[m]>key)        {            r=m-1;        }        else if(sum[m]=key)    {        return m-1;    }    else if(sum[m]>=key)    {        return m;    }    else    {        return m+1;    }}int query(int L,int R ,int l , int r , int tr ){    if(L<=l&&r<=R)    {        return node[tr];    }    int m=(l+r)>>1;    int ans=0;    if(L<=m)ans=query(L,R,l,m,tr<<1);    if(m

(编辑: lin375691011)

网友评论
相关文章