| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 19998 | Accepted: 7180 |
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 10
2 3
1 10
5 10
0
Sample Output
1
4
3
Source
- 题目中序列是非递增序列，这样有序的序列有利于我们减少搜查的数据量
- 我们可以利用相同数都在一起的性质给序列分块
- 然后对于一个询问，我们总是整块地查询
- 就是说对于一个查询我们先得出最左边分块出现次数和最右边分块出现次数，然后中间剩余分块可以用ST表RMQ查询
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 #include <climits> 7 #include <cmath> 8 #include <vector> 9 #include <queue> 10 #include <stack> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL ; 15 typedef unsigned long long ULL ; 16 const int maxn = 1e6 + 10 ; 17 const int inf = 0x3f3f3f3f ; 18 const int npos = -1 ; 19 const int mod = 1e9 + 7 ; 20 const int mxx = 100 + 5 ; 21 const double eps = 1e-6 ; 22 const double PI = acos(-1.0) ; 23 24 int fac[30], dp[maxn][30]; 25 int l[maxn], r[maxn]; 26 void ST(int n){ 27 int k=(int)(log((double)n)/log(2.0)); 28 for(int i=1;i<=n;i++) 29 dp[i][0]=r[i]-l[i]+1; 30 for(int j=1;j<=k;j++) 31 for(int i=1;i+fac[j]-1<=n;i++) 32 dp[i][j]=max(dp[i][j-1],dp[i+fac[j-1]][j-1]); 33 } 34 int RMQ(int u, int v){ 35 int k=(int)(log((double)(v-u+1))/log(2.0)); 36 return max(dp[u][k],dp[v-fac[k]+1][k]); 37 } 38 int n, m, u, v, ans, tot, a[maxn], b[maxn]; 39 int main(){ 40 // freopen("in.txt","r",stdin); 41 // freopen("out.txt","w",stdout); 42 for(int i=0;i<30;i++) 43 fac[i]=(1<<i); 44 while(~scanf("%d",&n)){ 45 if(0==n){break;} 46 scanf("%d",&m); 47 a[0]=1e6+1; 48 tot=0; 49 for(int i=1;i<=n;i++){ 50 scanf("%d",&a[i]); 51 if(a[i-1]!=a[i]){ 52 tot++; 53 b[i]=tot; 54 l[tot]=i; 55 r[tot]=i; 56 }else{ 57 b[i]=tot; 58 r[tot]++; 59 } 60 // b[i]=tot; 61 } 62 ST(tot); 63 while(m--){ 64 scanf("%d %d",&u,&v); 65 if(b[u]==b[v]){ 66 ans=v-u+1; 67 }else if(b[u]+1==b[v]){ 68 ans=max(r[b[u]]-u+1,v-l[b[v]]+1); 69 }else{ 70 ans=max(r[b[u]]-u+1,v-l[b[v]]+1); 71 ans=max(ans,RMQ(b[u]+1,b[v]-1)); 72 } 73 printf("%dn",ans); 74 } 75 } 76 return 0; 77 }
- 还没有人评论，欢迎说说您的想法！
客服
