一，单调栈

思想：

可以用于维护一个数前/后第一个大于/小于他的数。我们以维护最大值为例

1. 对于数x，求取它右边第一个大于他的数y。显然，[x,y]两个数中间的数都是比x小的。也就是，我们在求出x右边第一个大于它的数之前，一定能够先找到中间这些数的右边第一个比他大。（不可能超过y，因为中间数mid
2. 利用这个思想，我们把还未求出右边第一大的数放入栈里面，如果找到栈顶的右边第一大，弹出栈顶。否则，栈顶更新为这个更小的数（它一定不会比原栈顶慢找到右边第一大）
3. 那么如何求取左边第一大呢？显然，我们在比较栈顶时就已经实现比较了，求目前数x的左边第一大。
   1. 如果栈顶k比x大，显然k就是x的左边第一大（栈里面的元素显然都比k大，[k,x]之间不存在比k大的数，否则k早就被弹出了。
   2. 如果k小于x，等于k找到右边第一大，弹出k，继续比较x与新栈顶，直到栈空或者找到比k大。
   3. 但是你会发现，k等于x怎么办？我们可以在入栈时，记录每个元素栈里面比它严格大的值的下标，如果k=x，x存储k所记录的比他大的下标即可（可能没有）

P5788 【模板】单调栈 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include 
using namespace std;
#define ll               long long
#define endl             "n"
#define int              long long
#define endll            endl pii;
typedef pair pll;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
//double 型memset最大127，最小128
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 3e6 + 10;
int a[N];
void mysolve()
{
	stacks;
	int n,x;
	cin>>n;
	for(int i=1; i>x;
			while(!s.empty()&&s.top().first

 二，单调队列

单调队列的元素在按照进入顺序排序的同时维护了区间单调性。

P1886 滑动窗口 /【模板】单调队列 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1. 我们用单调队列维护最大值，即队列是递减的。队列存储的元素至多是包含当前位置的前k个数
2. 设当前遍历到i，值为x。如果x比队尾大，就删除队尾，直到队列空或者队尾比x大。（因为x比队列里的元素晚出现，所以队列里比他小的数，后面都没有他们什么事了）
3. 如果x比队尾小，放入队尾。
4. 注意，每次插入，先判断队首是否下标符合[i-k+1,i]的区间，否则舍去。

#include 
using namespace std;
#define ll               long long
#define endl             "n"
#define int              long long
typedef pair pii;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
//double 型memset最大127，最小128
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 3e5 + 10;

void mysolve()
{
	int n,k;
	cin>>n>>k;
	dequeq1,q2;
	vectora1,a2;
	int x;
	for(int i=1; i>x;
			if(ix)q2.pop_back();
					q2.push_back({x,i});
				}
			else
				{
					while(!q1.empty()&&q1.front().secondx)q2.pop_back();
					q2.push_back({x,i});
					a2.push_back(q2.front().first);
				}
		}
	for(int i=0; i> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

例题：P2698 [USACO12MAR]Flowerpot S 

1. 我们求区间[L,R]是否是合法区间，否则，显然是需要把区间继续扩大。
2. 所以，我们可以先固定L，不断往右移动R，显然第一个符合条件的R是最优的，那么，我们这时才把L往后移动。
3. 这样遍历只需O(n)。

#include 
using namespace std;
#define ll               long long
#define endl             "n"
#define int              long long
typedef pair pii;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
//double 型memset最大127，最小128
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 3e5 + 10;
pii a[N];
void mysolve()
{
	int n,d;
	cin>>n>>d;
	int ans=INF;
	for(int i=1; i>a[i].first>>a[i].second;
	dequeq1,q2;
	sort(a+1,a+1+n);
	int p=-1;
	for(int i=1; ia[i].second)q2.pop_back();
			q2.push_back({a[i].second,a[i].first});

			if(q1.front().first-q2.front().first>=d)
				{
					ans=min(ans,abs(q1.front().second-q2.front().second));//队列的队首就是整个队列下标最小的，所以最大值与最小值的L就是min那一个
					p=min(q1.front().second,q2.front().second);
					while(!q1.empty()&&q1.front().second> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: fl studio 需要什么配置，flstudio 21如何设置成中文

FL Studio 21是全功能的音乐工作站，漂亮的大混音盘，先进的制作工具，让你的音乐突破想象力的限制。FL Studio 21安装前需要先检查现有的系统配置要求是否符合软件要求。 fl studio 21需要什么配置 FL Studio for 21 Wi…