首页 > 代码库 > POJ3368Frequent values[RMQ 游程编码]
POJ3368Frequent values[RMQ 游程编码]
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 17581 | Accepted: 6346 |
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.
Sample Input
10 3-1 -1 1 1 1 1 3 10 10 102 31 105 100
Sample Output
143
Source
//// main.cpp// poj3368//// Created by Candy on 10/8/16.// Copyright © 2016 Candy. All rights reserved.//#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N=1e5+5,INF=1e9;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,q,l,r;int x,last,cnt=0,a[N],v[N],c[N],id[N],left[N],right[N];int st[N][20];void initRMQ(){ memset(st,0,sizeof(st)); for(int i=1;i<=cnt;i++) st[i][0]=c[i]; for(int j=1;(1<<j)<=cnt;j++) for(int i=1;i+(1<<j)-1<=cnt;i++) st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);}int rmq(int l,int r){ if(l>r) return 0; int k=log(r-l+1)/log(2); return max(st[l][k],st[r-(1<<k)+1][k]);}int main(int argc, const char * argv[]) { while((n=read())){ q=read(); memset(c,0,sizeof(c)); memset(left,0,sizeof(left)); memset(right,0,sizeof(right)); v[0]=v[n+1]=INF; for(int i=1;i<=n;i++){ v[i]=read(); if(v[i]==v[i-1]){ c[cnt]++; right[cnt]=i; id[i]=cnt; }else{ cnt++; a[cnt]=v[i]; c[cnt]++; left[cnt]=right[cnt]=i; id[i]=cnt; } } initRMQ(); //for(int i=1;i<=cnt;i++) printf("init %d %d %d %d\n",a[i],c[i],left[i],right[i]); for(int i=1;i<=q;i++){ l=read();r=read(); int ans=0; if(id[l]==id[r]) ans=r-l+1; else{ ans=max(right[id[l]]-l+1,r-left[id[r]]+1); ans=max(ans,rmq(id[l]+1,id[r]-1)); } printf("%d\n",ans); } } //printf("\n\n\n%d %d %d %d",id[1]+1,c[2],id[10]-1,rmq(id[1]+1,id[10]-1)); return 0;}
POJ3368Frequent values[RMQ 游程编码]