|
|
題目鏈接：http://poj.org/problem?id=3368
  /**//*
 題意：
給定一個(gè)長度為N(N <= 100000)的單調(diào)不降數(shù)列Si，然后是Q(Q <= 100000)條詢問
，問給定區(qū)間出現(xiàn)最多的數(shù)的次數(shù)。
解法：
離散化+線段樹 或者 離散化+RMQ
思路：
由于m很大，詢問的復(fù)雜度必須要log(n)，這樣一來就先確定下來是線段樹了，這個(gè)
題目有個(gè)限制條件，所有數(shù)都是單調(diào)不增的排列的，換言之，就是說如果兩個(gè)數(shù)相同的話
，他們之間的所有數(shù)必定也和它們相同。
于是就有了mlog(n)的算法：
對(duì)于所有的數(shù)均設(shè)定一個(gè)組號(hào)，也可以叫離散化吧，相同的數(shù)有相同的組號(hào)，然后將各個(gè)
數(shù)的頻率統(tǒng)計(jì)后記錄在一個(gè)數(shù)組中，表示該類數(shù)的大小，對(duì)于輸入的詢問[x, y]，直接查
詢它們在哪個(gè)組，分三種情況討論：
1. 如果x和y在一個(gè)組，那么最長長度就是y - x + 1
2. 如果組號(hào)相差1，那么找出兩者的分界點(diǎn)z(假設(shè)z點(diǎn)和x點(diǎn)組號(hào)相同)，那么答案就是Max
{z - x + 1, y - z}
3. 如果相差大于1，那么先將兩頭截掉，統(tǒng)計(jì)大的記錄，再和中間那段的最大值比較大小，
中間那段的最大值可以用線段樹或者RMQ區(qū)間查詢最值。
 */
#include <iostream>
using namespace std;
#define maxn 100010
typedef int Tree_Index;
struct Tree  {
int Max;
}T[maxn*4];
struct Pair {
int val;
int cnt;
}Pr[maxn];
int PrSize = 0;
int x[maxn], sum[maxn], pos[maxn];
int n, m;
void Build(int p, int l, int r) {
  if(l == r) {
T[p].Max = Pr[l].cnt;
return ;
 }
int mid = (l + r) >> 1;
Build(p<<1, l, mid);
Build(p<<1|1, mid+1, r);
T[p].Max = T[p<<1].Max > T[p<<1|1].Max ? T[p<<1].Max : T[p<<1|1].Max;
}
Tree_Index Query(int p, int l, int r, int a, int b) {
if(l == a && b == r) {
return p;
}
int mid = (l + r) >> 1;
if(b <= mid) {
return Query(p<<1, l, mid, a, b);
}else if(mid + 1 <= a){
return Query(p<<1|1, mid+1, r, a, b);
}else {
Tree_Index p1 = Query(p<<1, l, mid, a, mid);
Tree_Index p2 = Query(p<<1|1, mid+1, r, mid+1, b);
return T[p1].Max > T[p2].Max ? p1 : p2;
}
}
void ProcessPr() {
int i, j;
PrSize = 0;
for(i = 1; i <= n; i++) {
if(x[i] == x[i-1]) {
Pr[PrSize].cnt++;
}else {
PrSize++;
Pr[PrSize].val = x[i];
Pr[PrSize].cnt = 1;
}
}
for(i = 1; i <= n; i++) {
sum[i] = Pr[i].cnt + sum[i-1];
for(j = sum[i-1]+1; j <= sum[i]; j++)
pos[j] = i;
}
}
int findPos(int v) {
int l = 0;
int r = PrSize;
int ans = -1;
while(l <= r) {
int m = (l + r) >> 1;
if(v > sum[m]) {
l = m + 1;
if(m > ans)
ans = m;
}else
r = m - 1;
}
return ans + 1;
}
int main() {
int i;
x[0] = INT_MIN;
while(scanf("%d", &n) != EOF && n) {
scanf("%d", &m);
for(i = 1; i <= n; i++) {
scanf("%d", &x[i]);
}
ProcessPr();
Build(1, 1, PrSize);
while(m--) {
int x, y, l, r;
scanf("%d %d", &x, &y);
l = pos[x]; // findPos(x);
r = pos[y]; // findPos(y);
if(l == r) {
printf("%d\n", y - x + 1);
}else {
int ans = (sum[l] - x + 1) > (y - sum[r-1]) ? (sum[l] - x + 1) : (y - sum[r-1]);
if(l + 1 < r) {
Tree_Index p = Query(1, 1, PrSize, l+1, r-1);
if(T[p].Max > ans)
ans = T[p].Max;
}
printf("%d\n", ans);
}
}
}
return 0;
}
|