首页 技术 正文
技术 2022年11月24日
0 收藏 535 点赞 4,213 浏览 1557 个字

题意:求一段长度为n的序列里有多少个子区间内的最大值减最小值小于k。

解法:RMQ+尺取法或单调队列。RMQ可以用st或者线段树,尺取法以前貌似YY出来过……只是不知道是这个东西……

设两个标记l和r,对于区间[l, r]如果满足题中条件则ans+=(r – l + 1),然后r右移一位,直到不符合条件,将l左移,直到符合条件。

代码:

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
int MIN[100005 << 2], MAX[100005 << 2];
int a[100005];
void pushupMIN(int rt)
{
MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);
}
void pushupMAX(int rt)
{
MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if(l == r)
{
scanf("%d", &a[l]);
MIN[rt] = MAX[rt] = a[l];
return;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
pushupMIN(rt);
pushupMAX(rt);
}
int getMIN(int ll, int rr, int l, int r, int rt)
{
if(ll <= l && rr >= r)
return MIN[rt];
int res = INT_MAX;
int m = (l + r) >> 1;
if(ll <= m) res = min(res, getMIN(ll, rr, lson));
if(rr > m) res = min(res, getMIN(ll, rr, rson));
return res;
}
int getMAX(int ll, int rr, int l, int r, int rt)
{
if(ll <= l && rr >= r)
return MAX[rt];
int res = 0;
int m = (l + r) >> 1;
if(ll <= m) res = max(res, getMAX(ll, rr, lson));
if(rr > m) res = max(res, getMAX(ll, rr, rson));
return res;
}
int main()
{
int T;
while(~scanf("%d", &T))
{
int n, k;
while(T--)
{
scanf("%d%d", &n, &k);
build(1, n, 1);
int flag = 0;
int l = 1, r = 0;
LL ans = 0;
while(r <= n)
{
if(r == n || flag)
{
l++;
int tmp1 = getMIN(l, r, 1, n, 1);
int tmp2 = getMAX(l, r, 1, n, 1);
if(tmp2 - tmp1 < k)
{
ans += r - l + 1;
flag = 0;
if(r == n)
break;
}
}
else
{
r++;
int tmp1 = getMIN(l, r, 1, n, 1);
int tmp2 = getMAX(l, r, 1, n, 1);
if(tmp2 - tmp1 < k)
{
ans += r - l + 1;
if(r == n)
break;
}
else
flag = 1;
}
}
printf("%lld\n", ans);
}
}
return 0;
}

  

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141980.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:4,994
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,472
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,281
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,282
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,840
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,072
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站