POJ_3368_Frequent values

2018-06-17 21:46:45来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

Frequent values
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

Ulm Local 2007
 
  • 题目中序列是非递增序列,这样有序的序列有利于我们减少搜查的数据量
  • 我们可以利用相同数都在一起的性质给序列分块
  • 然后对于一个询问,我们总是整块地查询
  • 就是说对于一个查询我们先得出最左边分块出现次数和最右边分块出现次数,然后中间剩余分块可以用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("%d\n",ans);
74         }
75     }
76     return 0;
77 }

 

 

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【NOIP2016】天天爱跑步

下一篇:【luogu 1939】【模板】矩阵加速(数列)