EarlyOrders（单调栈）

题目链接&＃xff1a;点击这里

题目大意&＃xff1a;
给定 $n,k$ 和一个长度为 $n$ 的序列 ai(ai≤k)a_i(a_i\le k)ai​(ai​≤k) &＃xff0c;求一个 aia_iai​ 的子序列&＃xff0c;其包含 $1$ 到 $k$ 的所有数字各一个&＃xff0c;求这些子序列中字典序最小的子序列

题目分析&＃xff1a;
因为要求字典序最小的子序列&＃xff0c;其具有一定的单调性&＃xff0c;考虑使用单调栈维护序列
当我们要插入 aia_iai​ 时&＃xff0c;如果栈顶元素大小大于 aia_iai​ 且 存在 aj(i≤j)a_j(i\le j)aj​(i≤j) 等于栈顶元素&＃xff0c;就可以将栈顶元素弹出来减小栈中元素的字典序&＃xff08;因为后继还会出现栈顶元素所有不必担心弹出元素会导致最终序列缺少某个元素&＃xff09;
最终答案就是栈中的元素序列

具体细节见代码&＃xff1a;

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define int ll
using namespace std;
int read()
{int res &＃61; 0,flag &＃61; 1;char ch &＃61; getchar();while(ch<&＃39;0&＃39; || ch>&＃39;9&＃39;){if(ch &＃61;&＃61; &＃39;-&＃39;) flag &＃61; -1;ch &＃61; getchar();}while(ch>&＃61;&＃39;0&＃39; && ch<&＃61;&＃39;9&＃39;){res &＃61; (res<<3)&＃43;(res<<1)&＃43;(ch^48);//res*10&＃43;ch-&＃39;0&＃39;;ch &＃61; getchar();}return res*flag;
}
const int maxn &＃61; 2e5&＃43;5;
const int maxm &＃61; 3e4&＃43;5;
const int mod &＃61; 998244353;
const double pi &＃61; acos(-1);
const double eps &＃61; 1e-8;
int n,k,top,a[maxn],last[maxn],st[maxn];
bool vis[maxn];
signed main()
{n &＃61; read(),k &＃61; read();for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;) a[i] &＃61; read(),last[a[i]] &＃61; i;for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){if(vis[a[i]]) continue;while(st[top] > a[i] && last[st[top]] > i) vis[st[top--]] &＃61; false;st[&＃43;&＃43;top] &＃61; a[i];vis[a[i]] &＃61; true;}for(int i &＃61; 1;i <&＃61; k;i&＃43;&＃43;) printf("%d%c",st[i],i&＃61;&＃61;n ? &＃39;\n&＃39; : &＃39; &＃39;);return 0;
}