2015 多校赛 第一场 1002 (hdu 5289)
Description
Input
Output
Sample Input
Sample Output
Hint
First Sample, the satisfied groups include:[1,1]、[2,2]、[3,3]、[4,4] 、[2,3]
题意:给出数列长度 n 以及数字 k 以及数列,求出数列中所以满足其中最大值和最小值之差小于 k 的小数列的个数。注:单个数也算一个小数列且必然符合条件。
思路:
首先是查询区间最大值与最小值的方式——可以用树状数组,也可以用线段树,sparse-table由于空间限制不会用。
关于三者的特性——
st算法的复杂度 O(nlog(n)) / O(1) , 线段树为 O(nlog(n)) / (log(n)),树状数组 O(<nlog(n)) / O(log(n))
空间复杂度 st 为 O(nlog(n)), 线段树 O(n),常数较大 , 树状数组是 O(n)
编程上 st 和 树状数组 都比较容易实现,线段树代码较长
另外线段树灵活性较大
(引用自http://www.cnblogs.com/ambition/archive/2011/04/06/bit_rmq.html)
而后是遍历方式——从数列第一个数开始,并设指针 p 为1。如满足max-min<k,则++p,直到条件不满足。则此时有ans+=p-1(包含第一个数的所有组合)。之后第二个数同理,沿用指针 p ,因若第一个数满足条件,则第二个数也必然满足条件,以此类推。
遍历有小小的优化是,在判断++p后满足条件与否时,没必要调用query函数,直接以a[p]更新tmax和tmin即可。
优化后快 600ms。
代码如下:
(注意ans要用long long不然会wa。。)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=;
int n,k,t,a[maxn],maxval[maxn],minval[maxn],tmax,tmin;
int lowbit(int x){
return x&(-x);
}
void ini(){
for(int i=;i<=n;i++){
maxval[i]=minval[i]=a[i];
for(int j=;j<lowbit(i);j<<=){
maxval[i]=max(maxval[i],maxval[i-j]);
minval[i]=min(minval[i],minval[i-j]);
}
}
}
void query(int l,int r){
tmax=tmin=a[r];
while(true){
tmax=max(tmax,a[r]);
tmin=min(tmin,a[r]);
if(r==l) break;
for(r-=;r-l>=lowbit(r);r-=lowbit(r)){
tmax=max(tmax,maxval[r]);
tmin=min(tmin,minval[r]);
}
}
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--){
memset(maxval,,sizeof(maxval));
memset(minval,0x3f,sizeof(minval));
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
ini();
int p=;
long long ans=;
for(int i=;i<=n;i++){
if(p>n) p=n;
query(i,p);
while(tmax-tmin<k&&p<=n){
p++;
tmax=max(tmax,a[p]);
tmin=min(tmin,a[p]);
}
ans+=p-i;
}
printf("%I64d\n",ans);
}
return ;
}
最新文章
- 学习笔记总结---关于sass
- day06 Java面向对象
- [Unity菜鸟] 术语
- OC6_类方法
- Android 网络框架Volley的使用
- cf D. Queue
- struts2 实现过程和xml配置
- metaq spring
- 常用WebService一览表
- 老李秘技:loadrunner11.5支持net4.0么?
- 张高兴的 Windows 10 IoT 开发笔记:使用 MAX7219 驱动 8&#215;8 点阵
- swizzle method 和消息转发机制的实际使用
- Ant简介
- css浮动学习
- js深度复制三种方法
- 【UNIX环境高级编程】文件I/O
- 2019省赛训练组队赛3.31周四-17fj
- 使用LESS对CSS进行预处理
- 利用官方的vue-cli脚手架来搭建Vue集成开发环境
- 【Ansible 文档】【译文】动态inventory
热门文章
- ROS:Nvidia Jetson TK1开发平台
- OpenCV: 图像连通域检测的递归算法
- (转)Bootstrap 之 Metronic 模板的学习之路 - (1)总览
- kafka概述与下一代消息队列
- 查看占用某端口的进程——netstat、findstr 的使用
- Ubuntu下解压(unzip)乱码的解决方法
- NOIP2016 DAY2 T2蚯蚓
- [luogu 4886] 快递员
- while(Thread.activeCount() >; 1)
- __call__ 和 __str__ 魔术方法