传送门：P10878 [JRKSJ R9] 在相思树下 III

将军啊，早卸甲，他还在廿二，等你回家……

一道练习单调队列的好题 qwq

题目意思：

很明白了，不再复述。（注意 $ \forall i$ 表示对于任意的 i ，可理解为所有）

思路：

贪心是很明显的，因为我们要让最后的值最大，首先要把小的值删掉。
最后的答案就是进行 m 次操作 1 后的序列中的最小值。
考虑怎样求操作后的序列：

暴力：

枚举 + 判断 绝对TLE

正解

我们发现，操作后的序列中，第 \(i\) 项的值就是原序列中第 \(i\) 项到第 \(i+m\) 项中的最大值。好像可以用二分吗？
那么我们要做的就是查询每一个 \(i\) 到第 \(i+m\) 的最大值。

• 蒟蒻首先想到的是线段树。。我承认是线段树水题做多了
  维护线段树的区间最大值，枚举 \(i\) 从 \(1\) 到 \(n-m\) ，每次求 \(i\) 到 \(i+m\) 的最大值，再对所有最大值取最小。。（代码会在后面给）
• 但是还有更好的做法：单调队列，又称滑动窗口。放一道练手题：P1886 滑动窗口 /【模板】单调队列
  详解请往后翻 qwq
  这样就是个板子了。。。

详解 · 单调队列

队伍内元素保持单调性，保持的方法就是挤掉队尾不能保持单调性的元素。
可以通过双端队列 deque 来实现。
但是 zhx 曾曰过：STL 太慢了
所以给出一份手写的代码：

#include<bits/stdc++.h>

using namespace std;

int n,m;
int a[1001000];
int q[1000100];
int ans1[1000100];
int ans2[1000100];

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i]; 
	}
	int head=1,tail=0;
	for(int i=1;i<=n;i++)//单调上升
	{
		while(a[i]<a[q[tail]]&&head<=tail)tail--;
		q[++tail]=i;
		while(head<=tail&&q[head]<=i-m) head++;
		if(i>=m)cout<<a[q[head]]<<" ";
	}
	cout<<endl;
	memset(q,0,sizeof(q));
	head=1;tail=0;
	for(int i=1;i<=n;i++)//单调下降
	{
		while(a[i]>a[q[tail]]&&head<=tail)tail--;
		q[++tail]=i;
		while(head<=tail&&q[head]<=i-m) head++;
		if(i>=m)cout<<a[q[head]]<<" ";
	}
	return 0;
}

最终代码：

线段树：只需要有区间查询功能就可以了

#include<bits/stdc++.h>

using namespace std;

#define int long long //不开 long long 见祖宗

int m,n;
int a[1000100];
int minn=LLONG_MAX; //这个地方要用 long long 范围下的最大值，要不然会 WA 掉 1、2、4

struct node{
	int l,r;
	int maxn;
}z[4000100];

node operator+(const node &l,const node &r)
{
	node res;
	res.l=l.l,res.r=r.r;
	res.maxn=max(l.maxn,r.maxn);
	return res;
}

void build(int l,int r,int rt)
{
	if(l==r)
	{
		z[rt].l=z[rt].r=l;
		z[rt].maxn=a[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	z[rt]=z[rt<<1]+z[rt<<1|1];
}

int query(int l,int r,int rt,int nowl,int nowr)
{
	if(nowl<=l&&nowr>=r){
		return z[rt].maxn;
	}
	int mid=l+r>>1;
	if (nowl<=mid)
	{
		if (mid<nowr)
			return max(query(l,mid,rt<<1,nowl,nowr),query(mid+1,r,rt<<1|1,nowl,nowr));//这个地方依旧是我的重灾区 qwq
		else
			return query(l,mid,rt<<1,nowl,nowr); 
	}
	else
		return query(mid+1,r,rt<<1|1,nowl,nowr); 
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=n-m;i++)
	{
		int p=query(1,n,1,i,i+m);
		minn=min(minn,p);
	}
	cout<<minn<<endl;
	return 0;
}

单调队列：跟线段树对比来看码量好少

#include<bits/stdc++.h>

using namespace std;

#define int long long

int n,m;
int a[1000100];
int q[1000100];
int ans=LLONG_MAX;

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	int head=1,tail=0;
	m+=1;
	for(int i=1;i<=n;i++)//单调下降的序列，求最大值 
	{
		while(a[i]>a[q[tail]]&&head<=tail)tail--;
		q[++tail]=i;
		while(head<=tail&&q[head]<=i-m) head++;
		if(i>=m)ans=min(ans,a[q[head]]);
	}
	cout<<ans<<endl;
 }