傳送門
“棧”這個資料結構，想必大家都很熟悉，它滿足“後進先出”的性質。
squee_spoon做題的時候，有一種強迫症，即他總是先做最近的題目。例如，squee_spoon還沒有解決問題a的時候，看到了問題b，那麼他就會暫時放下a，先解決b。我們可以認為，squee_spoon做題總是嚴格滿足棧的性質。然而squee_spoon太弱了，總會有一大堆未解決的問題，在問題積壓數達到m的時候，他将難以維護他的“補題棧”，此時他不再接受新的問題（換句話說，他在任意時刻，最多存在m個未解決的問題）。
現在，squee_spoon拿到了一份題單，上面按順序列有n道題的題号p1~pn，求squee_spoon按順序讀題号的情況下，可能的字典序最小的做題順序。
題目要求字典序最小的做題順序，是以很容易有個樸素的想法，首先讓做的第一道題題号盡可能小，然後讓第二道題題号盡可能小……這樣得到的順序肯定是最小的。
順着這個思路往下想，有哪些題可以成為第一道呢，顯然是前m題都可以，因為“補題棧”的大小是m，你就可以一直讀到那一題，然後做掉，問題就轉化為了“求數組p在區間[1,m]的最小值”。同理，哪些題可以成為目前能做的題呢，自然是往後的某個區間（區間長度取決于目前棧被占用了多少空間），以及目前的棧頂。
每次要做的題就是能做的題裡面題号最小的那題，也就是相應區間的最小值和棧頂的值中更小的那個。于是這題的姿勢就是快速求區間最小值辣！比如線段樹（O(nlogn)），spare table（O(nlogn)），分塊（O(n^1.5)）都是可以過的。下面給一個線段樹的解法：
#include <bits/stdc++.h>
#define N
#define ll long long
using namespace std;
int a[N], seg_tree[N<<];
void build(int root, int left, int right){
if (left == right){
scanf("%d", &a[left]);
seg_tree[root] = a[left];
return ;
}
int mid = (left+right)>>;
build(root<<, left, mid);
build(root<<|, mid+, right);
seg_tree[root] = min(seg_tree[root<<], seg_tree[root<<|]);
}
int query(int root, int left, int right, int L, int R){
if (left <= L && right >= R){
return seg_tree[root];
}
int mid = (L+R)>>;
if (right <= mid) return query(root<<, left, right, L, mid);
else if (left > mid) return query(root<<|, left, right, mid+, R);
else return min(query(root<<, left, right, L, mid), query(root<<|, left, right, mid+, R));
}
stack<int> s;
bool first = true;
void Print(int x){
if (first){
first = false;
}else{
printf(" ");
}
printf("%d", x);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.txt", "r", stdin);
#endif
int n, m, i, j;
cin >> n >> m;
build(, , n);
for(i = ; i <= n; i++){
int l = i, r = i+m-s.size()-;
r = min(r, n);
int MIN = query(, l, r, , n);
if (s.size() && s.top() < MIN){
Print(s.top());
s.pop();
i--;
}else{
Print(MIN);
while(a[i] != MIN){
s.push(a[i]);
i++;
}
}
}
while(!s.empty()){
Print(s.top());
s.pop();
}
puts("");
return ;
}
以上内容轉自http://blog.csdn.net/squee_spoon/article/details/50985698