uva 11235-Frequent values(RMQ問題)
852 ワード
無降順配列の整数配列a 1,a 2を与えます.anさん、あなたの任務は一連の問い合わせ(i,j)に対して、ai,ai＋1と答えます.ajにおける出現回数が最も多い値の出現回数.
#include
#include
#include
#define mx 100000+10
#define max(x,y) (x)>(y) ? (x) : (y)
using namespace std;
int n,m,d[mx][18];
int a[mx],count[mx],num[mx],l[mx],r[mx];
void init()
{
int i,j;
for(i=0;iy) return 0;
int k=0;
while((1<a[i-1])
{
l[m++]=i;
if(i) r[m-2]=i-1;
}
num[i]=m-1;
count[m-1]++;
}
r[m-1]=i-1;
init();
while(q--)
{
scanf("%d%d",&i,&j);i--;j--;
if(num[i]==num[j])
{
printf("%d
",j-i+1);continue;
}
res=rmq(num[i]+1,num[j]-1);
res=max(res,r[num[i]]-i+1);
printf("%d
",max(res,j-l[num[j]]+1));
}
}
return 0;
}