Description
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.
题目就是求区间范围内出现最高的频率是多少。
用RMQ的话，统计某个数和这个之前的频率，然后询问的时候就是求两部分的最大值，第一部分是与x相同的数的个数，第二部分是第一个与x不同到y的部分，用RMQ求第二部分。
然后无力吐槽自己，logN数组开小了，结果一直WA，真是够傻逼的。
代码如下：
// ━━━━━━神兽出没━━━━━━
// ┏┓ ┏┓
// ┏┛┻━━━━━━━┛┻┓
// ┃ ┃
// ┃ ━ ┃
// ████━████ ┃
// ┃ ┃
// ┃ ┻ ┃
// ┃ ┃
// ┗━┓ ┏━┛
// ┃ ┃
// ┃ ┃
// ┃ ┗━━━┓
// ┃ ┣┓
// ┃ ┏┛
// ┗┓┓┏━━━━━┳┓┏┛
// ┃┫┫ ┃┫┫
// ┗┻┛ ┗┻┛
//
// ━━━━━━感觉萌萌哒━━━━━━ // Author : WhyWhy
// Created Time : 2015年07月17日 星期五 17时11分45秒
// File Name : 3368.cpp #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h> using namespace std; const int MaxN=; int dp[MaxN][];
int logN[MaxN]; //!!! void init(int N,int num[])
{
logN[]=-; for(int i=;i<=N;++i)
{
logN[i]=logN[i-]+((i&(i-))==);
dp[i][]=num[i];
} for(int j=;j<=logN[N];++j)
for(int i=;i+(<<j)-<=N;++i)
dp[i][j]=max(dp[i][j-],dp[i+(<<(j-))][j-]);
} int RMQ(int a,int b)
{
if(a>b)
return ; int k=logN[b-a+]; return max(dp[a][k],dp[b-(<<k)+][k]);
} int num[MaxN];
int rem[MaxN],wei[MaxN];
int N,Q; int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout); int a,b; while(~scanf("%d",&N) && N)
{
scanf("%d",&Q); rem[]=; for(int i=;i<=N;++i)
scanf("%d",&num[i]); for(int i=;i<=N;++i)
if(num[i]==num[i-])
rem[i]=rem[i-]+;
else
rem[i]=; wei[N]=N; for(int i=N-;i>=;--i)
if(num[i]==num[i+])
wei[i]=wei[i+];
else
wei[i]=i; init(N,rem); while(Q--)
{
scanf("%d %d",&a,&b);
printf("%d\n",max(RMQ(wei[a]+,b),min(wei[a],b)-a+));
}
} return ;
}