HDU1806 Frequent values

Problem Description You are given a sequence of n integers a₁ , a₂ , ... , a_n 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 a_i , ... , a_j .


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 a₁ , ... , a_n(-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+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

1
4
3
現將其離散化，那麼就轉化成連續區間最值，可用RMQ解決。
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    #include 
    using namespace std;
    const int maxn = 100000+10;
    vector 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<> 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;
    }