Frequent values_poj3368_rmq

NO IMAGE

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.

Input


The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , … , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, …, n}) separated by spaces. You can assume that for each i ∈ {1, …, n-1}: ai ≤ ai 1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.

The last test case is followed by a line containing a single 0.

Output


For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

Analysis


In order to ZHUANGBI I have decided to use English to write my analysis from now ;-P

Just kidding.

又是線段樹例題強行轉rmq

題目給出的是不降序,所以相鄰的相同項個數可以看成是這個數字的數量(語文水平低原諒措辭)
對於一段詢問可以拆成左右兩邊,右邊我們用ST直接求,左邊枚統計一下相同的數,這兩個的最大值就是答案

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
int f[100001][17],t[100001],c[100001];
int max(int x,int y)
{
return x>y?x:y;
}
int main()
{
int n,m;
while (scanf("%d",&n)&&n)
{
scanf("%d",&m);
for (int i=1;i<=n;i  )
{
scanf("%d",&t[i]);
c[i]=1;
if (t[i]==t[i-1])
c[i]=c[i-1] 1;
f[i][0]=c[i];
}
for (int j=1;j<=16;j  )
for (int i=1;i (1<<j)-1<=n;i  )
f[i][j]=max(f[i][j-1],f[i (1<<(j-1))][j-1]);
for (int i=1;i<=m;i  )
{
int x,y,cnt=0;
scanf("%d%d",&x,&y);
for (int j=x;j<=y&&t[j]==t[x];j  )
cnt  ;
x =cnt;
if (x>=y)
printf("%d\n",cnt);
else
{
int v=floor(log10(y-x 1)/log10(2));
int ans=max(cnt,max(f[x][v],f[y-(1<<v) 1][v]));
printf("%d\n",ans);
}
}
}
return 0;
}