UVA11235 - Frequent values（BMQ)
題目鏈接
題目大意：可以一串不遞減的序列，然后給你一個(gè)范圍L，R，要求你返回L，R出現(xiàn)最多次的那個(gè)值的出現(xiàn)次數(shù)。
解題思路：將這個(gè)序列重新編碼一下，把相同的數(shù)字標(biāo)記成一段，然后用num記錄是哪一段，用cnt記錄一下出現(xiàn)了多少個(gè)相同的。然后查詢的時(shí)候因?yàn)榭赡艹霈F(xiàn)從一段中的某個(gè)部分開始的情況，所以要先將頭和尾處理一下，標(biāo)記每一段的最左端和最右端位置。中間完整的部分用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網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
