首页 > 其他分享 >Sound(单调队列)

Sound(单调队列)

时间:2024-08-22 22:36:56浏览次数:11  
标签:Sound 10 typedef leq 队列 max long int 单调

题目描述
第一行有三个整数\(n,m,c(1\leq n\leq 10^6,1\leq m\leq 10^4,0\leq c\leq 10^4)\)。

第二行\(n\)个非负整数\(a_1,a_2,\dots,a_n(1\leq a_i\leq 10^6)\)。
求有多少个i满足[i...i+m-1]区间的极差<=c
输出
从小到大输出所有满足条件的\(i\),一行一个。如果没有\(i\)满足条件,则输出NONE。
样例输入 Copy
7 2 0
0 1 1 2 3 2 2
样例输出 Copy
2
6

简单的单调队列,所有的\(l_{i+1}>=l_{i}\),且\(r_{i+1}>=r{i}\)的问题都可以考虑单调队列,某些区间问题若离线后也可单调队列

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int a[N],q_max[N],q_min[N],Max[N],Min[N];
void solve()
{
	int n,m,c;
	cin>>n>>m>>c;
	int h_max = 1,t_max = 0;
	int h_min = 1,t_min = 0;
	for(int i=1;i<=n;++i) 
	{
		cin>>a[i];
		//对于j<k若k的条件完胜j则弹出j
		while(h_max<=t_max&&a[i]>=a[q_max[t_max]]) t_max--;
		while(h_min<=t_min&&a[i]<=a[q_min[t_min]]) t_min--;
		q_max[++t_max] = i;
		q_min[++t_min] = i;
		if(i>=m)
		{
			while(h_max<=t_max&&q_max[h_max]<i-m+1) h_max++;
			if(h_max<=t_max) Max[i] = a[q_max[h_max]];
			while(h_min<=t_min&&q_min[h_min]<i-m+1) h_min++;
			//cout<<h_min<<'\n';
			if(h_min<=t_min) Min[i] = a[q_min[h_min]];
		}
	}
	bool ok = false;
	for(int i=m;i<=n;++i) 
	{
		//cout<<i-m+1<<' '<<Max[i]<<' '<<Min[i]<<'\n';
		if(Max[i]-Min[i]<=c) ok = true,cout<<i-m+1<<"\n";
	}
	if(!ok) cout<<"NONE\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	//cin>>T;
	while(T--)
	{
		solve();
	}
}

标签:Sound,10,typedef,leq,队列,max,long,int,单调
From: https://www.cnblogs.com/ruoye123456/p/18374895

相关文章

  • 队列
    队列1.基本概念及描述队列也是一种特殊的线性表,队列的插入和删除在表的两端进行,插入的那端称为队尾,删除的那端叫做队首,插入和删除操作分别叫做进队和出队。生活中的排队购票现象就是队列的例子,先到先享受,队列具有“先进先出”(FirstInFirstOut)的特点.2.顺序队列及其实现C语......
  • 队列操作(深入理解FreeRTOS队列之队列实战)
    文章目录一、队列的操作二、学习总结在FreeRTOS中,队列的本质是环形缓冲区。一、队列的操作1、创建队列2、写队列3、读队列详细可看此篇博客:FreeRTOS——队列(基于百问网DshanMCU-F103实现挡球板游戏改造)-CSDN博客基于链表解析队列的使用:代码示例:#include"......
  • 单调栈和单调队列优化DP
    单调栈和单调队列优化DPluoguP1725琪露诺一道比较板的题明显是一个DP,则有\[{dp}_i=\max_{j=i-r}^{i-l}dp_j+a_i\]如果暴力则为\(O(n^2)\)但是发现\(\max_{j=i-r}^{i-l}dp_j\)就是单调队列所解决的问题,所以直接单调队列维护即可#include<bits/stdc++.h>#defineFAS......
  • Linux系统中利用消息队列实现两个进程的通信
    在Linux系统中进程间的通信有很多的方法,这次利用消息队列实现进程的通信进程一的代码实现#include<sys/types.h>#include<sys/ipc.h>#include<stdio.h>#include<sys/msg.h>#include<sys/types.h>#include<sys/ipc.h>#include<string.h>structmsgbuf{ ......
  • 高性能无锁队列 Disruptor 核心原理分析及其在i主题业务中的应用
    小结:生产者生产数据时,需要入队。消费者消费数据时,需要出队。入队时,不能覆盖没有消费的元素。出队时,不能读取没有写入的元素。因此,Disruptor中需要维护一个入队索引(生产者数据生产到哪里,对应AbstractSequencer中的cursor)和一个出队索引(所有消费者中消费进度最小的序号)。 ......
  • 数据结构:栈、队列详解篇
    数据结构:栈、队列详解篇一、栈(一)栈的概念(二)栈的实现1、结构定义2、功能实现(1)栈的初始化(2)栈的销毁(3)栈的扩容(4)压栈(5)出栈(6)取栈顶元素、判空、栈的大小(三)例题分析1、有效的括号题目分析二、队列(一)队列的概念(二)队列的实现1、结构定义2、功能实现(1)队列结点生成(2)队列初始......
  • C++ queue(STL queue,队列)用法详解
    只能访问queue<T>容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素,只能从头部移除元素。许多程序都使用了queue容器。queue容器可以用来表示超市的结账队列或服务器上等待执行的数据库事务队列。对于任何需要用FIFO准则处理的序列来说,使用queue容器适......
  • /* 线程读取循环队列*/
    /*线程读取循环队列*/#include<stdio.h>#include<stdlib.h>#include<pthread.h>#include<unistd.h>#defineQUEUE_SIZE5typedefstruct{intdata[QUEUE_SIZE];intfront;intrear;pthread_mutex_tlock;}CircularQueue......
  • 【模板】单调栈
    洛谷P5788【模板】单调栈单调栈就是使栈内元素单调递增或者单调递减的栈,单调栈也只能在栈顶操作。做一个比喻,比方说:有个集训队招人,一个数代表了一个选手的能力值,先进来的选手年龄会比较大,后面的选手年龄比较小,但是这个集训队没有人数限制,那么如果遇到一个比你小还比你强的人那......
  • 昇腾 - AscendCL C++应用开发 线程安全的队列
    昇腾-AscendCLC++应用开发线程安全的队列flyfishC++mutex各种各样的互斥锁mutex、timed_mutex、recursive_mutex、shared_mutexC++线程间同步的条件变量std::condition_variable和std::condition_variable_anyC++提供的智能指针unique_ptr、shared_ptr、wea......