HDU 1806 Frequent values（线段树+离散化+二分）

缺乏、安全感 2022-06-11 04:29 154阅读 0赞

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

题解：

这是今天比赛中唯一的一道数据结构题。。刚开始还以为很难，后来想到一个思路以后，调了一个多小时ac了，说一下思路：

题意：

给定一个不下降序列，给左右区间的端点坐标让你求该区间出现次数最多的数的次数

我把询问分成3组：

第一组是询问的两个端点值相同，的情况，假设端点为x，y，则长度就是y-x+1

第二组是两个端点中只有两种数字的情况，我们处理的时候保存下每种数字的开始的下标，然后第一种数字出现的次数就是第二种数字开始下标-x，第二种数字就是y-第该种数字的开始下标+1，答案就是两者间的最大值。

第三组就是除此之外的情况了

我们特殊处理两边端点的情况，两边用二分查找在离散后区间的下标，然后中间种类数字进行线段树操作，然后由于有负数出现，这里我用离散化进行处理（不懂的我数据结构题里面的扫描线有讲离散化，实质就是将一段数据的值进行映射，易于建树处理），然后离散化以后就是简单区间内求极值了，然后答案就是三者之中的最大值

思路是这样，但是模拟实现起来有一定难度

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    #define left k*2
    #define right k*2+1
    #define M (t[k].l+t[k].r)/2
    struct node
    {
        int l,r;
        int maxx;//放区间最大值
    }t[100005*4];
    int a[200005],b[100005],n,m,ans;//a数组放原始数据，b里面放离散后的数据（相当于每种数字保存一个）,ans表示离散后数字个数，相当于不同种数字个数
    int start[100005];//储存离散后第i个数在原始数组中最先开始的下标
    int num[100005];//储存离散后数字b[i]的个数
    void Build(int l,int r,int k)//基础的线段树求极值
    {
        t[k].l=l;
        t[k].r=r;
        if(t[k].l==t[k].r)
        {
            t[k].maxx=num[l];
            return;
        }
        int mid=(r+l)/2;
        Build(l,mid,left);
        Build(mid+1,r,right);
        t[k].maxx=max(t[right].maxx,t[left].maxx);
    }
    int query(int l,int r,int k)//日常询问
    {
        if(t[k].l==l&&t[k].r==r)
        {
            return t[k].maxx;
        }
        int mid=M;
        if(r<=mid)
            return query(l,r,left);
        else if(l>mid)
            return query(l,r,right);
        else
            return max(query(l,mid,left),query(mid+1,r,right));
    }
    int bin(int x)
    {
        int l=0,r=ans,mid=(l+r)/2;
        while(b[mid]!=x)
        {
            if(b[mid]>x)
                r=mid-1;
            else
                l=mid+1;
            mid=(l+r)/2;
        }
        return mid;
    }
    int main()
    {
        int i,j,k;
        while(scanf("%d",&n)!=EOF)
        {
            if(!n)
                break;
            memset(num,0,sizeof(num));
            scanf("%d",&m);
            ans=0;
            scanf("%d",&a[0]);//特殊处理下第一个输入
            num[0]=1;
            b[0]=a[0];
            start[0]=0;
            for(i=1;i<n;i++)
            {
                scanf("%d",&a[i]);
                if(a[i]!=a[i-1])//如果和前面的数字不一样
                {
                    ans++;
                    start[ans]=i;//存初始下标
                    b[ans]=a[i];//存离散后的情况
                }
                num[ans]++;
            }
            Build(0,ans,1);//建离散后的数
            int x,y;
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&x,&y);
                x--;y--;
                int l=bin(a[x]),r=bin(a[y]);
                if(a[x]==a[y])//两者值相同
                {
                    printf("%d\n",y-x+1);
                }
                else if(r-l==1)//如果为第二种情况，就是只有两种数字
                {
                    printf("%d\n",max(y-start[r]+1,start[r]-x));
                }
                else
                {
                    int d1=start[l+1]-x;//第一种数字在区间中的个数
                    int d2=y-start[r]+1;//第二种数字在区间中的个数
                    int ll=l+1;//去掉第一种数字后中间第一个数在离散后的下标
                    int rr=r-1;//倒数第二个离散后的下标
                    printf("%d\n",max(max(d1,d2),query(ll,rr,1)));//输出三者中的最大值
                }
            }
        }
        return 0;
    }