2021牛客暑期多校训练营5 K.King of Range (单调队列,双指针好题)
2021/8/2 6:06:14
本文主要是介绍2021牛客暑期多校训练营5 K.King of Range (单调队列,双指针好题),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
-
题意:有一长度为\(n\)的数组,问有多少子数组的最大值和最小值之差大于\(k\).
-
题意:看数据范围,这题比较稳的写法应该是\(O(n)\),考虑一个区间,如果当前区间的最大值最小值之差已经大于\(k\)了,那么我们再去移动右区间也一定是合法的,也就是没有意义的,那么此时固定左区间,右贡献为\(n-r+1\),之后我们再去移动左区间直到不合法为止,理解的关键点在于不合法的时候移动右区间,为什么不是移动左区间呢?废话,因为移动左区间的话区间在变小,也就是元素越来越少,你本来大的区间都不合法,小区间还想合法?具体实现就是两个单调队列记录最大值和最小值然后双指针维护区间.
-
代码:
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define me memset #define rep(a,b,c) for(int a=b;a<=c;++a) #define per(a,b,c) for(int a=b;a>=c;--a) const int N = 1e6 + 10; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; using namespace std; typedef pair<int,int> PII; typedef pair<ll,ll> PLL; ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;} ll lcm(ll a,ll b) {return a/gcd(a,b)*b;} int n,m,k; int a[N]; int q1[N],q2[N]; int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>m; rep(i,1,n) cin>>a[i]; while(m--){ cin>>k; int i=1; int hh1=0,tt1=-1,hh2=0,tt2=-1; ll ans=0; rep(j,1,n){ while(hh1<=tt1 && a[q1[tt1]]>=a[j]) tt1--; while(hh2<=tt2 && a[q2[tt2]]<=a[j]) tt2--; q1[++tt1]=j; q2[++tt2]=j; while(a[q2[hh2]]-a[q1[hh1]]>k){ i++; if(q1[hh1]<i) hh1++; if(q2[hh2]<i) hh2++; ans+=n-j+1; } } cout<<ans<<'\n'; } return 0; }
这篇关于2021牛客暑期多校训练营5 K.King of Range (单调队列,双指针好题)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?