POJ 3368 Frequent values RMQ ST算法/线段树
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了POJ 3368 Frequent values RMQ ST算法/线段树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4906字，纯文字阅读大概需要8分钟。
内容图文
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 15229 | Accepted: 5550 |
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
题意：
给你一个非递减序列。有m次询问，每次询问区间之间出现最多的数字出现的次数。
题解：
RMQ/线段树
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<cmath> #include<map> usingnamespace std ; typedef longlong ll; #define inf 100000 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } //******************************************************************struct ss{ int l,r,num,v; }a[100001]; int counts[100001]; int dp[100001][63],n,m,p; void rmq_init() { memset(dp,0,sizeof(dp)); for(int i=1;i<=p;i++){ dp[i][0]=counts[i]; } int k=floor(log((double)n+1)/log(2.0)); for(int j=1;j<=k;j++) { for(int i=1;i+(1<<j)-1<=p;i++) { int oo=i+(1<<(j-1)); dp[i][j]=max(dp[i][j-1],dp[oo][j-1]); } } } int RMQ(int x,int y) { int oo=floor(log((double)y-x+1)/log(2.0)); return max(dp[x][oo],dp[y-(1<<(oo))+1][oo]); } void work() { int l,r; for(int i=1;i<=m;i++) { scanf("%d%d",&l,&r); if(a[l].num==a[r].num){ cout<<r-l+1<<endl; } else { int ans=a[l].r-l+1; ans=max(r-a[r].l+1,ans); l=a[l].num+1; r=a[r].num-1; if(l<=r) ans=max(ans,RMQ(l,r)); cout<<ans<<endl; } } } void init() { int f=0,r=0,l=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i].v); if(f&&a[i].v!=a[i-1].v) { counts[p]=r-l+1; for(int j=l;j<=r;j++) a[j].num=p,a[j].l=l,a[j].r=r; r++; p++; l=r; } elseif(f){ r++; } if(f==0) { l=1; r=1,f=1; p=1; } } counts[p]=r-l+1; for(int j=l;j<=r;j++) a[j].num=p,a[j].l=l,a[j].r=r; // for(int i=1;i<=n;i++)cout<<counts[i]<<" ";} int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==0)break; init(); rmq_init(); work(); } return0; }
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<cmath> #include<map> usingnamespace std ; typedef longlong ll; #define inf 100000 inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } //******************************************************************struct ss { int l,r,v,num; }tr[100001*7],a[500001]; int counts[200001]; int n,m,p; void build(int k,int s,int t) { tr[k].l=s; tr[k].r=t; if(s==t){ tr[k].v=counts[s]; return ; } int mid=(s+t)>>1; build(k<<1,s,mid); build(k<<1|1,mid+1,t); tr[k].v=max(tr[k<<1].v,tr[k<<1|1].v); } int ask(int k,int s,int t) { if(s==tr[k].l&&t==tr[k].r) { return tr[k].v; } int mid=(tr[k].l+tr[k].r)>>1; if(t<=mid)return ask(k<<1,s,t); elseif(s>mid)return ask(k<<1|1,s,t); else { return max(ask(k<<1,s,mid),ask(k<<1|1,mid+1,t)); } } void init() { int f=0,l=0,r=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i].v); if(f&&a[i].v!=a[i-1].v) { counts[p]=r-l+1; for(int j=l;j<=r;j++)a[j].l=l,a[j].r=r,a[j].num=p; r++; l=r; p++; } elseif(f){ r++; } if(!f) { f=l=1; r=p=1; } } counts[p]=r-l+1; for(int j=l;j<=r;j++)a[j].l=l,a[j].r=r,a[j].num=p; ///for(int i=1;i<=p;i++)cout<<counts[i]<<" "; }int main() { while(scanf("%d%d",&n,&m)!=EOF) { p=0; if(n==0)break; init(); build(1,1,p); // cout<<p<<endl; int x,y; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(a[x].num==a[y].num){ cout<<y-x+1<<endl; } else { int ans=a[x].r-x+1; ans=max(ans,y-a[y].l+1); x=a[x].num+1; y=a[y].num-1; if(x<=y)ans=max(ask(1,x,y),ans); cout<<ans<<endl; } } } return0; }
原文：http://www.cnblogs.com/zxhl/p/4776577.html
内容总结
以上是互联网集市为您收集整理的POJ 3368 Frequent values RMQ ST算法/线段树全部内容，希望文章能够帮你解决POJ 3368 Frequent values RMQ ST算法/线段树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。