The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 3368 Frequent values(线段树+离散化)

最近在研究线段树这个数据结构,发现这东西还挺耐玩的,它没有固定的模式,具体的构建方法要依据不同题目的具体要求而定,虽然如此,不过大致的思路还是差不多,充其量不过改改节点里面的域罢了。
这题我看了半天,因为看到有区间了,而且数据量又很大,显然要用log L的算法,于是只能是线段树,可问题在于怎么维护这颗线段树?
由于给出的序列一定是非递减的,所以如果两个数字相同的话,它们中间的数字肯定相同。
具体的算法是这样的:
首先对给出的序列进行离散化统计,将相同的数字压缩成一个节点,然后统计出这个压缩后的节点在原序列中起点和终点的位置,以及出现的次数等。当然也要记录原数字在离散化后的序列中的位置。
之后就是查询,比方说[a,b]
1.如果a,b属于同一个组,那么区间长度就是我们想要的答案 b-a+1;
2.如果a,b组号相差1,说明该区间被中间截断了,只要分别研究两侧的区间,取大值即可Max(c-a+1,b-c) ---其中c是中间点---
3.如果a,b组号相差大于1,先取出两侧进行研究,取大值,然后再用线段树,算出中间区间的最大值,与刚才的那个数比较,取出最大值即可。


//This is the source code for POJ 3368
//Coded by abilitytao 
//Time:2009年7月24日21:03:20
//PS:This is the first time to using the method of discretization and the Data Structure Segment Tree to solve Problem.
//Worth to Memorize.
//Many thanks to the people on the Internet to share their codes.
//And Special thanks to the Blog owner "英雄哪里出来".
#include<iostream>
#include
<cmath>
#include
<cstring>
#include
<algorithm>
#include
<cstdio>
#include
<cstdlib>
using namespace std;
#define MAX 100010

struct point
{
    
int left;
    
int right;
    
int num;
    
int count;
}
p[MAX];//这个数组用来存储离散化之后点的信息


int myarray[MAX];
int n,q,T;
int hash[MAX];//第i个数在新的分组中的编号

struct Segnode
{

    
int num;//统计那个频率最高的数字
    int count;//统计频率最高的数字出现的次数
    Segnode *lchild;//指向左孩子
    Segnode *rchild;//指向右孩子
}
Segnodeset[MAX];//预先开辟很多节点以备使用,可以提升效率


Segnode 
*Newnode()
{
    
static int countnum=0;
    Segnode 
*temp=&Segnodeset[countnum++];
    temp
->lchild=NULL;
    temp
->rchild=NULL;
    
return temp;
}



void init()//离散化过程
{

    T
=1;
    p[T].left
=1;
    p[T].right
=1;
    p[T].count
=1;
    p[T].num
=myarray[1];
    hash[
1]=1;
    
int i;
    
for(i=2;i<=n;i++)
    
{

        
if(myarray[i]==myarray[i-1])
        
{
            p[T].count
++;
            p[T].right
=i;
        }

        
else
        
{
            T
++;
            p[T].num
=myarray[i];
            p[T].count
=1;
            p[T].left
=i;
            p[T].right
=i;
        }

        hash[i]
=T;
    }

}



Segnode 
*Build (int l,int r)//建立线段树,建立的同时统计区间上的最高频率
{
    Segnode 
*root=Newnode();
    
if(l==r)
    
{
        root
->count=p[l].count;
        root
->num=p[l].num;
        
return root;
    }


    
int mid=(l+r)>>1;
    root
->lchild=Build(l,mid);
    root
->rchild=Build(mid+1,r);
    
    
if(root->lchild->count  >  root->rchild->count)
    
{

        root
->num=root->lchild->num;
        root
->count=root->lchild->count;

    }

    
else
    
{

        root
->num=root->rchild->num;
        root
->count=root->rchild->count;
    }

    
return root;
}



int Query(Segnode *root,int a,int b,int l,int r)//查询函数
{

    
if(a==l&&b==r)
    
{

        
return root->count;
    }


    
int mid=(l+r)>>1;
    
if(b<=mid)
    
{

        
return Query(root->lchild,a,b,l,mid);
    }

    
else if(mid+1<=a)
    
{

        
return Query (root->rchild,a,b,mid+1,r);

    }

    
else
    
{

        
int x=Query(root->lchild,a,mid,l,mid);
        
int y=Query(root->rchild,mid+1,b,mid+1,r);
        
return x>y?x:y;
    }

}



int solve(Segnode *root,int a,int b)//算法核心在这个函数
{

    
if(hash[a]==hash[b])
    
{

        
return b-a+1;
    }
//如果查询的两个数在同一组中,很显然最大的频数应该等于区间长度

    
else if(hash[a]+1==hash[b])
    
{

        
int l=p[hash[a]].right-a+1;
        
int r=b-p[hash[b]].left+1;
        
return l>r?l:r;
    }
//如果组号相差一,则中间有分段点,截断之后取大的

    
else
    
{

        
int l=p[hash[a]].right-a+1;
        
int r=b-p[hash[b]].left+1;
        
int MAXNUM=l>r?l:r;

        
int ans=Query(root,hash[a]+1,hash[b]-1,1,T);
        
return MAXNUM>ans?MAXNUM:ans;

    }


}


inline 
void put(int x)//用字符串输出,用以节省OI时间 PS:不过貌似作用不大
{
    
if(x< 0)
    
{
        putchar(
'-');
        x 
= -x;
    }

    
if(x == 0){
        putchar(
'0');
        
return;
    }

    
char s[20];
    
int bas = 0;
    
for(;x;x/=10)s[bas++= x%10+'0';
    
for(;bas--;)putchar(s[bas]);
    
return;
}




int main()
{

    
int i;
    
int a,b;
    Segnode 
*root;
    
while(scanf("%d",&n))
    
{
        
if(n==0)
            
break;
        scanf(
"%d",&q);
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d",&myarray[i]);
        }

        init();
        root
=Build(1,T);
        
while(q--)
        
{

            scanf(
"%d%d",&a,&b);
            put(solve(root,a,b));
            putchar(
'\n');

        }

    }

    
return 0;
}


posted on 2009-07-24 21:31 abilitytao 阅读(1703) 评论(1)  编辑 收藏 引用

评论

# re: POJ 3368 Frequent values(线段树+离散化) 2009-07-25 15:49 凡客诚品

路过看看!支持下!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理