? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??Frequent?values

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?TimeLimit:3000Ms

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?Specification

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?Specification

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

題意：給出一個非降序排列的數組A1，A2，A3，……，An，對于一系列詢問（i，j），輸出Ai，A(i+1)，……，Aj中出現次數最多的值出現的次數。

分析：因為整個數組是非降序的，所有相等元素會聚集在一起，這樣就可以把這個數組進行游標編碼，比如-1,1,1,2,2,2,4就可以編碼成（-1,1），（1,2），（2,3），（4,1），其中（a，b）表示有b個連續的a。用value[i]和count[i]分別表示第i段的數值和出現次數，num[p]、left[p]、right[p]分別表示位置p所在段的編號和左右端點位置，則每次查詢時的結果為以下三部分的最大值：從L到L所在段的結束處的元素個數（即right[L]-L+1）、從R所在段的開始處到R處的元素個數（即R-left[R]+1）、中間第num[L]+1段到第num[R]-1段的count的最大值。這樣問題就幾乎轉化為了RMQ問題。

#include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<iostream> using namespace std; const int N = 1e5 + 10; int n, tot, Q; int dp[N][20]; int num[N], cnt[N], Left[N], Right[N]; void RMQ_Init() {memset(dp, 0, sizeof(dp));for(int i = 1; i <= tot; i++)dp[i][0] = cnt[i];for(int j = 1; (1<<j) <= n; j++)for(int i = 1; i + (1<<j) - 1 <= tot; i++)dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } int RMQ(int L, int R) {if(L > R)return 0;int k = 0;while((1<<(k+1)) <= R - L + 1) k++;return max(dp[L][k], dp[R-(1<<k)+1][k]); } int main() {int v, last_v, i;while(~scanf("%d",&n)){if(n == 0) break;scanf("%d",&Q);tot = 0;memset(Left, 0, sizeof(Left));memset(Right, 0, sizeof(Right));memset(cnt, 0, sizeof(cnt));for(i = 1; i <= n; i++){scanf("%d",&v);if(i == 1){++tot;last_v = v;Left[tot] = 1;}if(last_v == v){num[i] = tot;cnt[tot]++;Right[tot]++;}else{num[i] = ++tot;cnt[tot]++;Left[tot] = Right[tot] = i;last_v = v;}}RMQ_Init();int L, R;for(int i = 0; i < Q; i++){scanf("%d%d",&L,&R);if(num[L] == num[R])printf("%d\n", R - L + 1);else{int tmp1 = Right[num[L]] - L + 1;int tmp2 = R - Left[num[R]] + 1;int tmp3 = RMQ(num[L] + 1, num[R] - 1);printf("%d\n",max(tmp1, max(tmp2, tmp3)));}}}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA 11235 Frequent values（RMQ）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。