首页 > 代码库 > HDU1806 Frequent values

HDU1806 Frequent values

2024-07-03 04:13:41   219人阅读

Problem 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
现将其离散化，那么就转化成连续区间最值，可用RMQ解决。
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <queue>
    using namespace std;
    const int maxn = 100000+10;
    vector<int> val,cnt;
    int res[maxn][20];
    int num[maxn],lft[maxn],rgt[maxn];
    int n,q;
    void init_RMQ(){
        int nt = cnt.size();
        for(int i = 0; i < nt; i++) res[i][0] = cnt[i];
        for(int j = 1; (1<<j) <= nt; j++){
            for(int i = 0; i+(1<<j)-1 < nt; i++)
                res[i][j] = max(res[i][j-1],res[i+(1<<(j-1))][j-1]);
        }
    }
    int RMQ(int L,int R){
        int k = 0;
        while((1<<(k+1)) <= R-L+1) k++;
        return max(res[L][k],res[R-(1<<k)+1][k]);
    }
    int main(){

        int t,now;
        while(cin >> n &&n){
            cin >> q;
            val.clear();
            cnt.clear();
            scanf("%d",&now);
            cnt.push_back(1);
            for(int i = 1; i < n; i++){
                int t;
                scanf("%d",&t);
                if(t==now)
                    cnt[cnt.size()-1]++;
                else{
                    now = t;
                    cnt.push_back(1);
                }
            }
            init_RMQ();
            int cur = 0;
            for(int i = 0; i < cnt.size(); i++){
                int tl = cur,tr = cur+cnt[i]-1;
                for(int j = 0; j < cnt[i]; j++){
                    num[cur] = i;
                    lft[cur] = tl;
                    rgt[cur++] = tr;
                }
            }

            while(q--){
                int L,R;
                scanf("%d%d",&L,&R);
                if(L > R) swap(L,R);
                L--;R--;
                int sta = num[L],ed = num[R];
                if(sta==ed){
                    printf("%d\n",R-L+1);
                    continue;
                }
                int ans = max(rgt[L]-L+1,R-lft[R]+1);
                sta++;
                ed--;
                if(sta<=ed)
                    ans = max(ans,RMQ(sta,ed));
                printf("%d\n",ans);
            }
        }
        return 0;
    }



联系
我们