UVA11235 - Frequent values（BMQ)
題目鏈接
題目大意：可以一串不遞減的序列，然后給你一個范圍L，R，要求你返回L，R出現最多次的那個值的出現次數。
解題思路：將這個序列重新編碼一下，把相同的數字標記成一段，然后用num記錄是哪一段，用cnt記錄一下出現了多少個相同的。然后查詢的時候因為可能出現從一段中的某個部分開始的情況，所以要先將頭和尾處理一下，標記每一段的最左端和最右端位置。中間完整的部分用BMQ。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
const int N = 1e5 + 5;
const int M = 20;
int left[N], right[N];
int A[N];
struct Num {
int value, count;
Num (const int value = 0, const int count = 0): value(value) , count(count) {}
};
vector<Num> v;
map<int, int> num;
int d[N][M];
int n;
void RMQ_init () {
int l = v.size();
for (int i = 0; i < l; i++)
d[i][0] = v[i].count;
for (int j = 1; (1<<j) <= l; j++)
for (int i = 0; i + (1<<j) - 1 < l; i++)
d[i][j] = max (d[i][j - 1], d[i + (1<<(j - 1))][j - 1]);
}
int RMQ (int l, int r) {
int k = 0;
while ((1<<(1 + k)) <= (r - l + 1)) k++;
return max (d[l][k], d[r - (1<<k) + 1][k]);
}
int main () {
int q;
while (scanf ("%d", &n) && n) {
scanf ("%d", &q);
v.clear();
num.clear();
for (int i = 0; i < n; i++) {
scanf ("%d", &A[i]);
if (v.size() && v[v.size() - 1].value == A[i])
v[v.size() - 1].count++;
else {
num[A[i]] = v.size();
v.push_back(Num(A[i], 1));
left[num[A[i]]] = i;
}
}
for (int i = 0; i < v.size(); i++)
right[num[v[i].value]] = left[num[v[i].value]] + v[i].count - 1;
RMQ_init();
int l, r;
int ans;
while (q--) {
scanf ("%d%d", &l, &r);
l--;
r--;
if (A[l] != A[r]) {
ans = max (right[num[A[l]]] - l + 1, r - left[num[A[r]]] + 1);
if (num[A[l]] + 1 <= num[A[r]] - 1)
ans = max (ans, RMQ(num[A[l]] + 1, num[A[r]] - 1));
} else
ans = r - l + 1;
printf ("%d
", ans);
}
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創(chuàng)，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
