hdu 1806 ， pku3368 Frequent values

时间：2011-05-11 来源：奋斗青春

题意：

给n个数，已经按从大到小顺序排列好，一共有q个询问，每次询问一个区间，问这个区间中出现次数最多的数是什么。题目数据范围：数的个数，1 <= n <= 100000 询问次数，1 <= q <= 100000 每个数的大小，-100000 <= ai <= 100000 很容易想到建立线段树，并在线段树的每个节点中保存区间中出现次数最多的数需要解决的问题，两个子结点的信息如何合并到父节点。很显然，子结点中出现次数最多的数不一定就是父节点中出现次数最多的数，有可能一个数在两个子结点中的出现次数都不是最多，但是子结点合并成父节点后，这个数的出现次数就最多了考虑到题目中的重要条件，数组中的数是有序的！当左子节点区间最右的数与右子区间最左的数相等时，这个相等的数的出现次数可能最多需要记录节点区间最左和最右的数的信息

我的想法就是定义一个结构体： struct node{ int l,r; int count,num; int lcount,lnum; int rcount,rnum; }; l,r存该节点的边界。 count存该节点中出现最多的数字的个数，num存该节点中出现最多的数字。 lcount 存该节点左端连续出现的数字的个数， lnum存该节点左端连续出现的数字。 rcount 存该节点右端连续出现的数字的个数， rnum存该节点右端连续出现的数字。建树的时候初始化的时候比较麻烦一点，每次询问的时候不是很麻烦。。代码：

# include<stdio.h>
# include<string.h>
# define N 100005
struct node{
        int r,l;
        int num,count;
        int rnum,rcount;
        int lnum,lcount;
}tree[4*N];
int a[N],MAX;
void bulid(int l,int r,int t)//建树
{
        int mid,ans;
        tree[t].l=l;
        tree[t].r=r;
        if(l==r) 
        {
                tree[t].count=tree[t].lcount=tree[t].rcount=1;
                tree[t].num=tree[t].lnum=tree[t].rnum=a[l];
                return;
        }
        mid=(l+r)/2;
        bulid(l,mid,2*t);
        bulid(mid+1,r,2*t+1);

        if(tree[2*t].count>=tree[2*t+1].count) 
        {
                tree[t].num=tree[2*t].num;
                tree[t].count=tree[2*t].count;
        }
        else 
        {
                tree[t].num=tree[2*t+1].num;
                tree[t].count=tree[2*t+1].count;
        }
        tree[t].lnum=tree[2*t].lnum;
        tree[t].lcount=tree[2*t].lcount;
        tree[t].rnum=tree[2*t+1].rnum;
        tree[t].rcount=tree[2*t+1].rcount;
        if(tree[2*t].rnum==tree[2*t+1].lnum)
        {
                ans=tree[2*t].rcount+tree[2*t+1].lcount;
                if(ans>tree[t].count) 
                {
                        tree[t].count=ans;
                        tree[t].num=tree[2*t].rnum;
                }
                if(tree[2*t+1].lnum==tree[2*t].lnum) tree[t].lcount+=tree[2*t+1].lcount;
                if(tree[2*t].rnum==tree[2*t+1].rnum) tree[t].rcount+=tree[2*t].rcount;
        }
}
void updata(int l,int r,int t)
{
        int mid,ans1,ans2;
        if(tree[t].l==l && tree[t].r==r) 
        {
                if(tree[t].count>MAX) MAX=tree[t].count;
                return;
        }
        if(r<=tree[2*t].r) updata(l,r,2*t);
        else if(l>=tree[2*t+1].l) updata(l,r,2*t+1);
        else
        {
                mid=tree[2*t].r;
                updata(l,mid,2*t);
                updata(mid+1,r,2*t+1);
                if(tree[2*t].rnum == tree[2*t+1].lnum) 
                {
                        if(a[l]!=tree[2*t].rnum) ans1=tree[2*t].rcount;
                        else ans1=mid-l+1;
                        if(a[r]!=tree[2*t+1].lnum) ans2=tree[2*t+1].lcount;
                        else ans2=r-mid;
                        if(ans1+ans2 > MAX) MAX=ans1+ans2;
                }
        }
}
int main()
{
        int i,Q,start,end,n;
        while(scanf("%d",&n)!=EOF && n)
        {
                scanf("%d",&Q);
                for(i=1;i<=n;i++)
                        scanf("%d",&a[i]);
                bulid(1,n,1);
                while(Q--)
                {
                        scanf("%d%d",&start,&end);
                        if(start==end) {printf("1\n");continue;}
                        MAX=0;
                        updata(start,end,1);
                        printf("%d\n",MAX);
                }
        }
        return 0;
}