POJ 3368.Frequent values-处理数据+RMQ(ST)
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 20960 | Accepted: 7403 |
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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1e5+;
int f[maxn],num[maxn],mm[maxn][];
int n;
void ST(){
for(int i=;i<=n;i++)
mm[i][]=num[i];
int k=floor(log((double)n+)/log(2.0));//最多能走2的多少次方
for(int j=;j<=k;j++){
for(int i=;i+(<<j)-<=n;i++)
mm[i][j]=max(mm[i][j-],mm[i+(<<(j-))][j-]);
}
}
int RMQ(int l,int r){
if(l>r)return ;
int k=floor(log((double)(r-l+))/log(2.0));
return max(mm[l][k],mm[r-(<<k)+][k]);
}
int main(){
int q,a,b;
while(~scanf("%d",&n)&&n){
scanf("%d",&q);
for(int i=;i<=n;i++){
scanf("%d",&f[i]);
if(i==){
num[i]=;continue;
}
if(f[i]==f[i-])
num[i]=num[i-]+;
else
num[i]=;
}
ST();
while(q--){
scanf("%d%d",&a,&b);
int t=a;
while(t<=b&&f[t]==f[t-])t++;//处理一下连续的数对查询的影响,找到第一次出现的数的位置
int cnt=RMQ(t,b);
int ans=max(t-a,cnt);//将查询出来的最大值和开头跳过去的数的次数比较一下
printf("%d\n",ans);
}
}
return ;
}
总之,RMQ好像很厉害的样子,好多东西变形一下就可以用RMQ写,溜了,在写HDU的3183,写好之后写题解。
好菜啊,难受。
最新文章
- easyui_动态添加隐藏toolbar按钮
- iOS案例:读取指定目录下的文件列表
- JRE、JDK和JVM之间的关系
- Python学习第二天数组
- 用ES6语法和方式写gulp
- python 多线程,进程的理解
- 201521123098 《Java程序设计》第14周学习总结
- mysql生成20万条数据(连表插入)
- AspNetCore taghelpers标签的使用
- Flutter数据持久化入门以及与Web开发的对比
- sse矩阵乘法 应该是1毫秒纯运算1000次
- 对比JavaScript中的Continue和Break
- JavaEE 之 Spring Data JPA
- 使用虚拟机VM12安装REHL7
- ARC设置
- solr服务器搭建与Tomact整合及使用
- stopManagedWebLogic.sh强制关闭Managed Server
- hive与hbase的整合
- cuowu
- 使用 csc.exe 编译C#代码
热门文章
- LNMP的环境搭建
- 【Spring】事务的实现方式
- paper:synthesizable finite state machine design techniques using the new systemverilog 3.0 enhancements 之 standard verilog FSM conding styles(二段式)
- json_encode() 避免转换中文
- 设置vim 永久显示行号
- 文件上传下载,命令之wget / curl / which / sort / uniq / cut / wc /tr /sed
- luogu3371 【模板】单源最短路径 dijkstra堆优化
- Maven项目下Tomcat插件选择方法
- deque 类
- ThinkPHP5杂技(一)