POJ_3368_Frequent values
2018-06-17 21:46:45来源:未知 阅读 ()
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("%d\n",ans); 74 } 75 } 76 return 0; 77 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- POJ-3278 2020-04-01
- Asteroids!_poj2225 2020-02-09
- poj-1753题题解思路 2020-01-26
- POJ1852 2019-11-11
- POJ2431 优先队列+贪心 - biaobiao88 2019-11-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash