單調佇列的操作
不妨用一個問題來說明單調佇列的作用和操作：
不斷地向buffer里讀入元素，也不時地去掉最老的元素，不定期的詢問當前buffer里的最小的元素。
最straightforward的方法：普通佇列實現buffer。
進隊出隊都是O(1)，一次查詢需要遍歷當前佇列的所有元素，故O(n)。
堆頂始終是最小元素，故查詢是O(1)。
而進隊出隊，都要調整堆，是O(logn)。
使用Segment Tree或sparse Table，線段樹沒寫過(樹狀數組用過)，是logn級的；稀疏表不懂，只知道是logn級的。對於這類問題這兩種方法也搞得定，但是沒有本文主人公來得快。
單調佇列的舞台由於單調佇列的隊頭每次一定最小值，故查詢為O(1)。
進隊出隊稍微複雜點：
進隊時，將進隊的元素為e，從隊尾往前掃描，直到找到一個不大於e的元素d，將e放在d之後，捨棄e之後的所有元素；如果沒有找到這樣一個d，則將e放在隊頭(此時佇列里只有這一個元素)。
出隊時，將出隊的元素為e，從隊頭向後掃描，直到找到一個元素f比e後進隊，捨棄f之前所有的。(實際操作中，由於是按序逐個出隊，所以每次只需要出隊只需要比較隊頭)。
每個元素最多進隊一次，出隊一次，攤排分析下來仍然是 O(1)。
上面的話可能還是沒能講出單調佇列的核心：佇列並不實際存在的，實際存在的是具有單調性的子序列。對這個子序列按心中的佇列進行操作，譬如在進隊時丟棄的元素，雖然它不存在於這個子序列里，但是還是認為他存在於佇列里。
POJ 2823是一個典型的單調佇列題，不過因為題目要求中大量的輸入輸出的使得時間要求竟然卡scanf和printf的字元串解析(直接實現要5000ms)，害得我極其猥瑣的手動輸入輸出解析(800+ms)，真是不爽。
另外進隊的順序和出隊的順序並不一定相同，因為這個佇列本身是隱含存在的，可以在進隊時看成一個佇列，出隊時看成另一個佇列，只要出隊的元素在佇列中就行。可以想像成一個佇列只有頭和身，另一個佇列只有身和尾，而這身是共用的。
在信息學競賽的一些套用
先介紹單調佇列
做動態規劃時常常會見到形如這樣的轉移方程：
f[x] = max or min{g(k) | b[x] <= k < x} + w[x]
(其中b[x]隨x單調不降，即b[1]<=b[2]<=b[3]<=...<=b[n])
(g[k]表示一個和k或f[k]有關的函式，w[x]表示一個和x有關的函式)
這個方程怎樣求解呢？我們注意到這樣一個性質：如果存在兩個數j, k，使得j <= k，而且g(k) <= g(j)，則決策j是毫無用處的。因為根據b[x]單調的特性，如果j可以作為合法決策，那么k一定可以作為合法決策，又因為k比j要優，（注意：在這個經典模型中，“優”是絕對的，是與當前正在計算的狀態無關的），所以說，如果把待決策表中的決策按照k排序的話，則g(k)必然是不降的。
這樣，就引導我們使用一個單調佇列來維護決策表。對於每一個狀態f(x)來說，計算過程分為以下幾步：
1、 隊首元素出隊，直到隊首元素在給定的範圍中。
2、 此時，隊首元素就是狀態f(x)的最優決策，
3、 計算g(x)，並將其插入到單調佇列的尾部，同時維持佇列的單調性（不斷地出隊，直到佇列單調為止）。
重複上述步驟直到所有的函式值均被計算出來。不難看出這樣的算法均攤時間複雜度是O(1)的。因此求解f(x)的時間複雜度從O(n^2)降到了O(n)。
單調佇列指一個佇列中的所有的數符合單調性（單調增或單調減），在信息學競賽的一些題目上套用，會減少時間複雜度
例題：廣告印刷（ad.pas/c/cpp）
【問題描述】
最近，afy決定給TOJ印刷廣告，廣告牌是刷在城市的建築物上的，城市裡有緊靠著的N個建築。afy決定在上面找一塊儘可能大的矩形放置廣告牌。我們假設每個建築物都有一個高度，從左到右給出每個建築物的高度H1,H2…HN，且0<Hi<=1,000,000,000，並且我們假設每個建築物的寬度均為1。要求輸出廣告牌的最大面積。
【輸入檔案】
中的第一行是一個數n (n<= 400,000 ）
第二行是n個數，分別表示每個建築物高度H1,H2…HN，且0<Hi<=1,000,000,000。
【輸出檔案】
輸出檔案 ad.out 中一共有一行，表示廣告牌的最大面積。
【輸入樣例】
6
5 8 4 4 8 4
【輸出樣例】
24
【解釋】各個測試點一秒，
但就這道題來說，n<= 400,000，我們如果用枚舉不會過全部數據，我們應設計出o(n)的算法來解決，這是單調佇列就可以派上用場了。
具體做法是 先正著掃一遍，再倒著掃一遍，找到每一個數的右極限與左極限，最後找出最大值。
program bensen;
var
temp,ans:int64;
n,p,q,i,j:longint;
a:array[0..400000] of longint;
b,r,l:array[0..400000] of longint;
begin
readln(n);
for i:=1 to n do
read(a[i]);
p:=1;q:=0;
for i:=1 to n+1 do
begin
while (p<=q) and (a[i]<a[b[q]]) do
begin
r[b[q]]:=i;
dec(q);
end;
inc(q);b[q]:=i;
end;
fillchar(b,sizeof(b),0);
p:=1;q:=0;
for i:=n downto 0 do
begin
while (p<=q) and (a[i]<a[b[q]]) do
begin
l[b[q]]:=i;
dec(q);
end;
inc(q);b[q]:=i;
end;
for i:=1 to n do
begin
temp:=(r[i]-l[i]-1)*a[i];
if temp>ans then ans:=temp;
end;
writeln(ans);
end.
