|
|
题目链接：http://poj.org/problem?id=3368
  /**//*
 题意：
给定一个长度为N(N <= 100000)的单调不降数列Si，然后是Q(Q <= 100000)条询问
，问给定区间出现最多的数的次数。
解法：
离散化+线段树 或者 离散化+RMQ
思路：
由于m很大，询问的复杂度必须要log(n)，这样一来就先确定下来是线段树了，这个
题目有个限制条件，所有数都是单调不增的排列的，换言之，就是说如果两个数相同的话
，他们之间的所有数必定也和它们相同。
于是就有了mlog(n)的算法：
对于所有的数均设定一个组号，也可以叫离散化吧，相同的数有相同的组号，然后将各个
数的频率统计后记录在一个数组中，表示该类数的大小，对于输入的询问[x, y]，直接查
询它们在哪个组，分三种情况讨论：
1. 如果x和y在一个组，那么最长长度就是y - x + 1
2. 如果组号相差1，那么找出两者的分界点z(假设z点和x点组号相同)，那么答案就是Max
{z - x + 1, y - z}
3. 如果相差大于1，那么先将两头截掉，统计大的记录，再和中间那段的最大值比较大小，
中间那段的最大值可以用线段树或者RMQ区间查询最值。
 */
#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;
}
|