蒟蒻的單調隊列orz，真的蒻

（……打了這麼久orz我今天才知道這玩意是啥意思……）

沒有老師就是飄啊……我居然學完樹狀數組和線段樹連個隊列都不會……orz orz orz

這篇是單調隊列哦，不是優先隊列（優先隊列那種東西queue不就好了嘛）

咳咳咳廢話說的真多，回到正題

什麼是單調隊列

咳咳咳反正是給自己看的，直接舉個例子吧，比如一個從小到大的單調隊列，那麼這個隊列中的每個元素的下标應符合遞增，每個元素也應該符合遞增

跟優先隊列的差別應該是能看出來的吧……優先隊列基本上就是排序好的數組了……（其實這麼說，隻是因為我不知道該怎麼解釋）

單調隊列的算法思想

原始數組

下标	1	2	3	4	5
值	4	2	5	6	3

假如我們現在要将這整個數組加入從小到大的單調隊列q

首先隊列必備的兩個指針：head  tail

隊列本來為空，是以第一個元素直接入隊，tail++

下标	1
值	4

第二個元素2要入隊了，但這時候我們發現2<4，那麼如果将2直接加入隊列，顯然不符合其遞增的單調性，是以我們幹掉它的前一個元素（嘤嘤嘤就是這麼暴力），tail--，再把2入隊，tail++

下标	1
值	2

第三個元素是5,5>2，符合其單調性，是以5直接入隊tail++

下标	1	2
值	2	5

第四個元素是6，同上一步

下标	1	2	3
值	2	5	6

最後一個元素是3，同第二步，若要将3加入隊列，不僅要幹掉前面的6，tail--，前面的5也不能留！tail--（嗯就是這麼兇）

這時候的隊列就變成了這個樣子

下标	1	2
值	2	3

ok，操作完成啦✿✿ヽ(°▽°)ノ✿

代碼實作

結合我們剛剛的算法思想，我們就可以來搞一搞代碼了QwQ

（s數組儲存的是下标）

#include<bits/stdc++.h>
using namespace std;
int a[1000100],q[1000100],s[1000100]; 
int main()
{
	int n,k,tail,head;
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	head=1;
	tail=0;
	for (int i=1;i<=n;i++)
	{
	//	cout<<"現在出場的是："<<i<<endl; 
		while (tail>=head&&a[i]<=q[tail])
		{
	//		cout<<"出隊(tail)："<<s[tail]<<' '<<q[tail]<<endl;
			tail--;
		}
		tail++;
		q[tail]=a[i];
		s[tail]=i;
		while (s[head]<i-k+1)
		{
	//		cout<<"出隊(head):"<<s[head]<<' '<<q[head]<<endl;
			head++;
		}
	//	cout<<"現在的隊首是"<<s[head]<<"   "<<q[head]<<endl;
		if (i>=k)
			printf("%d ",q[head]);
	} 
	printf("\n");
	head=1;
	tail=0;
	for (int i=1;i<=n;i++)
	{
		q[i]=0;
		s[i]=0;
	}
	for (int i=1;i<=n;i++)
	{
	//	cout<<"現在出場的是："<<i<<endl; 
		while (tail>=head&&a[i]>=q[tail])
		{
	//		cout<<"出隊(tail)："<<s[tail]<<' '<<q[tail]<<endl;
			tail--;
		}
		tail++;
		q[tail]=a[i];
		s[tail]=i;
		while (s[head]<i-k+1)
		{
	//		cout<<"出隊(head):"<<s[head]<<' '<<q[head]<<endl;
			head++;
		} 	
	//	cout<<"現在的隊首是"<<s[head]<<"   "<<q[head]<<endl;
		if (i>=k)
			printf("%d ",q[head]);
	} 
	printf("\n");
	return 0;
}
           

我手頭上沒有純裸題QwQ（其實就是懶QwQ）（咳咳主要是快下課了我想趕緊把這篇寫完）

這篇是【傳送門】洛谷1886 滑動視窗 的AC代碼

其實就是兩個裸單調隊列加上隊首出隊操作而已，挺裸的一道題

（PS：調程式的時候我才知道！原來scanf不加&會.exe停止運作！printf加了&會輸出奇奇怪怪的東西！！！（好吧其實還是我蒻））

但我在這裡強烈安利一位大佬的題解QwQ！我就是看着他的題解學的單調隊列！這裡貼一下位址以便自己以後膜或者大家參觀QwQ（我這慘淡的通路量到底是哪來的信心……）https://www.luogu.org/blog/hankeke/solution-p1886

好啦！完結撒花✿✿ヽ(°▽°)ノ✿

【總有一天我會把我學過的所有算法和所有寫過的模闆題都寫成部落格的！！！這是一個 假 真flag】