单调栈¶
单调栈简介¶
单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。
例题 #1¶
大意
给定序列\(a\)，求每个\(a_i\)它前面的第二个比他大的数的下标。
对于这种问题，我们应该想到使用单调栈来实现。
单调栈只能处理\(a_i\)前面第一个比他大的数字（实现：记一个递减的栈，插入一个数时先把栈顶比它小的都弹出），那么我们就跑两边单调栈。第一遍记录\(a_i\)前面第一个比他大的数字，记其下标为\(v_i\)，第二次我们找到\(a_{v_i}\)前面第一个比他大的数字，然后我们从\(a_1\)扫描到\(a_n\)，输出\(a_{v_i}\)前面第一个比他大的数字即可。
Code
/*////////ACACACACACACAC///////////
. Coding by Ntsc .
. ToFind Chargcy .
. Prove Yourself .
/*////////ACACACACACACAC///////////
//头文件
#include<bits/stdc++.h>
//数据类型
#define ll long long
#define ull unsigned long long
#define db double
#define endl '\n'
//命名空间
using namespace std;
//常量
const int N=1e6+5;
const int M=1e6+5;
const int MOD=903250223;
const int INF=1e9;
//变量
int n,b,c,a[N],y[N],tmp,k,cnt,mxr;
int stk[N],ans[N],top;
vector<int> v[N];
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
cin>>a[i];
while(top&&a[i]>a[stk[top]])top--;
v[stk[top]].push_back(i);//记录前面第一个比它大的
stk[++top]=i;
}
top=0;//清空栈
for(int i=1; i<=n; i++) {
for(int j=0; j<v[i].size(); j++) {
while(top&&a[v[i][j]]>a[stk[top]])top--;//单调栈
ans[v[i][j]]=stk[top];//由之前记录的第一个比它大的往前找到第2个比它大的
}
stk[++top]=i;
}
for(int i=1; i<=n; i++)printf("%d\n",ans[i]+1);
#ifdef PAUSE_ON_EXIT
system("pause");
#endif
return 0;
}
例题 #2 City Game¶
题目描述
Bob爱上了一个策略游戏（Simcity？）游戏中一个城市由k个地区组成，每个地区都是一块长N×宽M大小的网格矩形,其中可能有些网格已被占用，用R表示;有些则是空地，用F表示。
游戏中可以在空着的空间上建一个矩形的建筑，同时每个建筑按它所占的空地网格数来收租，每占用一个网格可收租金3美元。Bob想知道每个地区中最大面积建筑物能收多少租金。
n,m (n,m<= 1000)
要求O(nm)。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T stk,Args... args) {
if constexpr (enable_dbg){
cerr << stk;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e3 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int a[N][N],h[N][N];
int top;
pii stk[N];
void solve(){
int n=rd,m=rd;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;
cin>>c;
if(c=='F')a[i][j]=1;
}
}
itn ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j])h[i][j]=h[i-1][j]+1;
}
}
for(int i=1;i<=n;i++){
top=0;
stk[++top]=mp(h[i][1],1);
for(int j=2;j<=m;j++){
int w=0;
while(top&&h[i][j]<=stk[top].pf){
w+=stk[top].ps;
ans=max(ans,stk[top].pf*w);
top--;
}
stk[++top]=mp(h[i][j],w+1);
}
int w=0;
while(top){
w+=stk[top].ps;
ans=max(ans,stk[top--].pf*w);
}
}
cout<<ans*3<<endl;
memset(a,0,sizeof a);
memset(h,0,sizeof h);
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=rd;
while(T--){
solve();
}
return 0;
}
例题 #3 奶牛排队¶
题目描述
奶牛在熊大妈的带领下排成了一条直队。
显然，不同的奶牛身高不一定相同……
现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 \(A\) 是最矮的，最右边的 \(B\) 是最高的，且 \(B\) 高于 \(A\) 奶牛。中间如果存在奶牛，则身高不能和 \(A,B\) 奶牛相同。问这样的奶牛最多会有多少头？
从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 \(0,2\)，但不会是 \(1\)）。
对于全部的数据，满足 \(2 \le N \le 10^5\)，\(1 \le h_i <2^{31}\)。
看上去貌似没有单调性，因此我们不可以用单调队列来维护了。那么那些区间可能称为答案呢？
我们考虑如果b可能作为答案，那么b应该是某个后缀最大值。否则我们选择它后面的那个后缀最大值明显更优。
那么a呢？应该是某个后缀最小值。否则可能无法满足要求。
那么我们从前往后扫一遍，同时维护当前这个前缀的后缀max和后缀min。在寻找答案时，只需要在后缀min里面找到离最后一个后缀max最远，又是在倒数第二个后缀max之后的那个后缀min，它们之间的就是可能的答案。
那么如果维护后缀max？单调栈可以使用。
// Problem: P6510 奶牛排队
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6510
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define itn int
int read(){
int x;
cin>>x;
return x;
}
const int N=2e5+5;
const ull P=137;
/*
策略
A.. B
A一定是后缀min
B一定是后缀max
用单调栈维护后缀信息
*/
int topmn,topmx,mn[N],mx[N];
int h[N];
int ans;
signed main(){
int n=rd;
for(int i=1;i<=n;i++){
h[i]=rd;
}
for(int i=1;i<=n;i++){
while(topmx&&h[mx[topmx]]<h[i])topmx--;
while(topmn&&h[mn[topmn]]>=h[i])topmn--;
int loc=lower_bound(mn+1,mn+topmn+1,mx[topmx])-mn;
if(loc<=topmn)ans=max(ans,i-mn[loc]+1);
mx[++topmx]=i;
mn[++topmn]=i;
}
cout<<ans<<endl;
}
例题 #4 单调栈优化\(n^3\)扫描线 长方形¶
题目描述
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。
为了简化问题，小明做出如下规定：
（1）这张纸的长宽分别为 \(n,m\)。小明将这张纸看成是由\(n\times m\)个格子组成，在剪的时候，只能沿着格子的边缘剪。
（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。
（3）剪出来的长方形的大小没有限制。
小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？
输入格式
第一行两个正整数 \(n,m\)，表示这张纸的长度和宽度。
接下来有 \(n\) 行，每行 \(m\) 个字符，每个字符为 * 或者 .。
字符 * 表示以前在这个格子上画过，字符 . 表示以前在这个格子上没画过。
输出格式
仅一个整数，表示方案数。
对 \(100\%\) 的数据，满足 \(1\leq n\leq 1000,1\leq m\leq 1000\)
如果枚举上界下界，然后扫描线，那么是O(n3)的。但是我们使用单调栈可以优化到O(n2)。
我们的O(n^2)使用在枚举右下角的坐标上。画图示意：
// Problem: P1950 长方形
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1950
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
//
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long
#define pb push_back
#define itn int
#define ps second
#define pf first
#define rd read()
int read()
{
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
for (auto v: a) cerr << v << ' ';
err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
cerr << a << ' ';
err(x...);
}
#else
#define dbg(...)
#endif
const int N=2e3+5;
const ull P=137;
const int INF=1e18+7;
/*
策略
*/
string s[N];
int h[N][N];
int top;
pair<int,int> stk[N];
signed main(){
int n=rd,m=rd;
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]=" "+s[i];
}
for(int i=1;i<=m;i++){
int pre=0;
for(int j=1;j<=n;j++){
if(s[j][i]=='*')pre=j;
else h[j][i]=j-pre;
}
}
int ans=0;
for(int i=1;i<=n;i++){
top=0;
int res=0;
for(int j=1;j<=m;j++){
int wid=0;
while(top&&stk[top].pf>=h[i][j]){
wid+=stk[top].ps;
res-=stk[top].pf*stk[top].ps;
top--;
}
stk[++top]={h[i][j],wid+1};
res+=h[i][j]*(wid+1);
ans+=res;
}
}
cout<<ans<<endl;
}