栈 属于 一种最基本的数据结构 具体的 维护一个一个序列 且这个序列中的元素满足先进后出 或者 后进先出类似于火车进站 可以想象一下。
而单调的栈 具有一些性质：
1 单调栈里的元素具有单调性
2 元素被加入到栈前 会在栈顶把破坏栈单调性的元素都删除。
3 使用单调栈可以找到元素向左遍历第一个比他小的元素 也可以找到元素向左遍历第一个比他大的元素。（显然 这是单调性的应用吧）
当然 也有一些其他栈的变形 辅助贪心 如 LIS 维护数列的性质 ：可持久化单调栈 什么的。还有一些比较有意思的是 对顶栈维护整个序列。栈还和卡特兰数有关 这些坑都填一下吧。
对顶栈：LINK:HDU4699
题目意思让你维护一个数列和一个光标 有多个操作 模拟每个操作 并输出对应结果。Q<=1e6
I x 在光标位置插入一个x 插入完后光标移动到x之后 D 删除光标前一个数字 L 光标向左移 R 光标向右移 Q k 在k之前的最大前缀和 且k不超过当前光标位置。
这个题目很有意思由于动态的插入数字我们可以考虑BST 或者 treap splay 。我乍一看是splay 维护区间位置尽管这样做也可以但是对于Q k 的询问呢？设f[i]表示i之前的前缀最大值 s[i]表示前i个数的和。
那么显然有 s[i]+=s[i-1] f[i]=max(f[i-1].s[i]); 由于每次询问都是在光标之前我们可以只维护光标之前的这个东西 并且光标每次至多移动1个位置我们可以动态的维护这个东西了。
复杂度Qlogn 不过写起来会比较麻烦也没有必要 但是貌似没有更好的解决方法了 此时栈的作用就非常的大了。
当然也可以叫做对顶队列 我们发现 由于每次都是动态插入 维护一个 队列的话每次移动是O(n)的 由于每次只在光标处+数字所以可以维护两个队列一个是光标前的一个是光标后的。这样做就舒服多了。
wa 了近乎3次 我是真的菜 操作可能不合法 f[0]=-INF 多组数据 直接怀疑人生啊 这就是菜鸡的表现没有认真读题（题目是英文的我懒得多看两眼...
//#include<bits/stdc++.h> #include<iostream> #include<ctime> #include<cstdio> #include<cmath> #include<cctype> #include<cstring> #include<string> #include<queue> #include<stack> #include<deque> #include<map> #include<set> #include<bitset> #include<algorithm> #include<utility> #include<vector> #include<iomanip> #include<cstdlib> #define INF 2000000000 #define min(x,y) ((x)>(y)?(y):(x)) #define max(x,y) ((x)>(y)?(x):(y)) #define db double #define RE register #define EPS 1e-8 #define ll long long #define ull unsigned long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=1000010; int Q; char c[5]; int top,top1; int a[MAXN],b[MAXN],f[MAXN],s[MAXN]; int main() { //freopen("1.in","r",stdin); while(scanf("%d",&Q)==1) { top=top1=0;f[0]=-INF; for(int i=1;i<=Q;++i) { int x; scanf("%s",c+1); if(c[1]=='I') { x=read(); a[++top]=x; s[top]=s[top-1]+a[top]; f[top]=max(f[top-1],s[top]); } if(c[1]=='D')--top; if(c[1]=='L') { if(!top)continue; b[++top1]=a[top]; --top; } if(c[1]=='R') { if(!top1)continue; a[++top]=b[top1]; s[top]=s[top-1]+a[top]; f[top]=max(f[top-1],s[top]); --top1; } if(c[1]=='Q') { x=read(); printf("%d ",f[x]); } } } return 0; }
值得一提的是这种方法的复杂度是O(n) 的而且还好写。值得推荐。
卡特兰数：是组合数学中一个长出现在各种计数问题的数列。(前两天某人hzk还叫我去学组合数学...的确到现在才发现数据结构就是坑 学多了没好处 不如来点思维的感受一下思考的快乐。
卡特兰数 数列 ： 1 1 2 5 14 42 132 429...看出来什么没貌似没有很显然的递推关系 的确很难确定一个公式 因为这个公式是个组合数 光看的话显然很难看出来。
Cn =C0Cn-1+C1Cn-2+...Cn-1C0（n>=2）其中C0=1 C1=1; 哇这原来是一个对称的式子。这意味着 我们之间去递推好像是n^2的。
1 卡塔兰数就是研究栈的问题的。栈的问题模型：给出n个数1~n 和一个栈。每个数都要进出栈一次如果进入栈的顺序是 1,2,3,...n那么可能的出栈序列有多少种。
其中 上述Cn 就是 n个数 答案。(这个公式 找规律应该是可以找到的吧不过看起来有点困难...
自然有通项公式(斐波那契都有通项这个怎么会没有：Cn=c(2n,n)-c(2n,n+1)通过非常简单的变换可得->Cn=C(2n,n)/(n+1);
众所周知求组合数 的复杂度可以是O(n)的 那么这个求Cn得复杂度也可以是O(n)的。
考虑为什么这个问题的答案会是Cn呢？关于证明 见算法进阶P49 。
2 这个还和二叉树构成有关 问n个节点 能构成多少棵不同的二叉树 因为编号不影响结果 所以考虑中序遍历 根节点为第k个出栈 那么就是左边的Ck-1*Cn-k这东西其中k取0~n-1那么就和上述式子一毛一样了。
3 凸多边形的三角形划分。这里就比较玄学了 我看网上有的说的感觉不太对...下面是我的理解 由于划分的顺序和 划分的数量无关我们先选择一条边作为划分基底。
此时连边 以基底为三角形的底边 划分 左边形成一个i边形 右边形成一个 n-i+2变形 其中(i>=3)可以显然 问题规模不断缩小（至少缩小1...
其实就是 Cn=Ci*C(n-i+2) 其中i€[3,n-1] 令ti=c(i+3) ti=上述式子 感觉很稳...（口胡的,,,
4
5
6
7
还有这么多 我看不下去了 往后了...
表达式计算 中缀表达式就那样O(n)的求 不会的话见 代码（luogu 1054）
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<iomanip> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<algorithm> #include<cctype> #include<utility> #include<set> #include<bitset> #include<queue> #include<stack> #include<deque> #include<map> #include<vector> #include<ctime> #define INF 2147483646 #define ll long long #define R register #define mod 131 using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int MAXN=55; char s[MAXN]; int n,sl,pos; char c[MAXN][MAXN]; int flag[MAXN],vis[MAXN]; stack<int>num; stack<char>op; void get(char *a) { for(int i=0;i<=52;i++)a[i]=' '; char c=getchar();pos=0; while(c==' '||c==' ') c=getchar(); while(c!=' '&&c!=' ') { a[++pos]=c; c=getchar(); } } inline int fast_pow(int b,int p) { int ans=1; for(int i=1;i<=p;++i)ans=ans*b%mod; return ans; } inline void js() { int x=num.top()%mod,ss;num.pop(); int xx=num.top()%mod;num.pop(); char w=op.top();op.pop(); if(w=='+')ss=x+xx; if(w=='-')ss=xx-x; if(w=='*')ss=x*xx%mod; if(w=='^')ss=fast_pow(xx,x); num.push(ss%mod); } inline int calc(int x,char *w,int len) { while(num.size())num.pop(); while(op.size())op.pop(); for(int i=1;i<=len+1;++i)op.push('('); w[len+1]=')'; for(int i=1;i<=len+1;++i) { if(w[i]==' ')continue; //cout<<w[i]<<endl; if((w[i]>='0'&&w[i]<='9')||w[i]=='a') { if(w[i]=='a'){num.push(x);continue;} int s=w[i]-'0'; while(w[i+1]>='0'&&w[i+1]<='9') { s=s*10+w[i+1]-'0'; ++i; } num.push(s%mod); } else { if(w[i]=='(')op.push(w[i]); if(w[i]=='+'||w[i]=='-') { while(op.top()!='(')js(); op.push(w[i]); } if(w[i]=='*') { while(op.top()=='*'||op.top()=='^')js(); op.push(w[i]); } if(w[i]=='^') { while(op.top()=='^')js(); op.push(w[i]); } if(w[i]==')') { while(op.top()!='(')js(); op.pop(); } } } return (num.top()%mod+mod)%mod; } int main() { //freopen("1.in","r",stdin); //scanf("%s",s+1); get(s);sl=pos; //for(int i=1;i<=sl;++i)cout<<s[i]; n=read(); for(int i=1;i<=n;++i)get(c[i]),flag[i]=pos; for(int i=1;i<=10;++i) { int ans=calc(i,s,sl); //cout<<ans<<endl; for(int j=1;j<=n;++j) { if(vis[j])continue; if(ans!=calc(i,c[j],flag[j]))vis[j]=1; //cout<<calc(i,c[j],flag[j])<<endl; } //printf("%d ",ans); } for(int i=1;i<=n;++i) { if(vis[i])continue; printf("%c",char('A'+i-1)); } return 0; }
单调栈：
LINK：SP1805
求水平线上最大矩阵面积。n<=100000;考虑答案的必要性 下界max{每一个矩形的面积}。
考虑矩形联系起来怎么统计到答案上 貌似不好搞 分类讨论一下分析答案的存在性：全部都是递增的矩形。那么答案为每一个矩形的长*后面连续矩形的宽。
考虑递减的矩形 倒着来重复刚才的过程。但是为了得到一个普遍解我们不能倒着来 找到正着的一个普遍寻找规律的答案线索。遇到一个自己比上一个矩阵小 那么就不要上一个矩阵累积中间被弹出矩阵的宽度。
最后答案为 每个矩阵长*前面被弹出的矩阵宽度。这还不够优秀 因为上一个矩阵比当前高那么除了他本身给上上一个带来的贡献 它自己就不能再形成贡献了 扔掉 然后把它看成和我一样高的东西。
考虑参差不齐的矩形（也就是正解）：obviosly 我们可以把这一段矩形 看成先递增后递减...然后呢？栈里维护单调递增的矩形就好了。
//#include<bits/stdc++.h> #include<iostream> #include<ctime> #include<cstdio> #include<cmath> #include<cctype> #include<cstring> #include<string> #include<queue> #include<stack> #include<deque> #include<map> #include<set> #include<bitset> #include<algorithm> #include<utility> #include<vector> #include<iomanip> #include<cstdlib> #define INF 1000000000 #define min(x,y) ((x)>(y)?(y):(x)) #define max(x,y) ((x)>(y)?(x):(y)) #define db double #define RE register #define EPS 1e-8 #define ll long long #define ull unsigned long long using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline ll read() { ll x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const ll MAXN=100010; ll n,top,ans; ll a[MAXN],s[MAXN],w[MAXN]; int main() { //freopen("1.in","r",stdin); while(1) { n=read();ans=0; if(!n)break; for(ll i=1;i<=n;++i)a[i]=read(); a[n+1]=-1;s[0]=-1;top=0; for(ll i=1;i<=n+1;++i) { if(a[i]>=s[top]) { s[++top]=a[i]; w[top]=1; } else { ll p=0; while(a[i]<s[top]) { p+=w[top]; ans=max(ans,s[top]*p); --top; } s[++top]=a[i];w[top]=p+1; } } printf("%lld ",ans); } return 0; }
LINK: luogu3722
影魔...取自dota 没玩过 不说了 题目大意 一个区间 每次询问a b询问这个区间中有一些合法的点对可以对答案造成贡献具体是这样的对于一个i j 来说设c=max(a{i+1,j-1});c<=ai&&c<=aj时贡献为p1 c大于其中一项小于其中其中的一项时贡献p2 求a b这个询问的答案。
其想让我们区间快速数点对 简称区间数点这类问题不是树状数组就是线段树考虑如何写这道题。
我们考虑固定左端点快速查找右端点O(n)的时间内由a扫向b 设当前位置为k 推到这里我们寻常的思路就走不通了因为区间不同带来的最大值也不同...
看了一眼神犇写的东西 考虑每个最大值给答案带来的贡献为什么要说每个？对于一个i来说其最大值的有效区间我们给他求出来l[i] r[i] 向左向右延伸的第一个大于ai的东西。
这个东西可以带来的有效点对是什么 显然l[i] r[i]->p1 l[i]~(i+1~r[i])->p2 r[i]~(i-1~l[i])->p2 对了还有一个i,i+1->p1
于是 发现每次贡献显然是一个区间 如果每次至少有一个定点 算作一个定点上 那么贡献称矩形 对于一个询问a 和b 我们其实对于横坐标限制a b 纵坐标限制a b 最终框起来的这个东西的贡献就好了。（扫描线qwq...好久没写了我也不会写了...怎么办发现每次都有定点我们建一个前缀和线段树类似于主席树然后不断继承前面的版本然后+区间修改就完成了。
至于l[i]和r[i]这个东西当然是由单调栈来求 yy一下就出来了...(原来快速数点分两个层面一个是左端点数右端点 一个是每个点对答案的区间贡献...
好题 这个可持久化的线段树 区间修改是不能pushdown的(在上一个的基础之上 而单点修改对空间消耗不大可以把一条链都给改了 空间复杂度每次增长logn 而区间修改想想pushdown 一下子要增加若干个节点 对空间以及时间消耗非常恐怖 此时建议标记永久化就可以解决这个问题了 一次修改标记区间至多logn吧 开节点也是这么多 稳定！
在此基础上yy一下 主席树查询第k大区间修改怎么办好像不太能写 此时考虑分块吧以后会写了说似乎YNOI上有这毒瘤题...
码了很久的code 一次通过了对标记永久化的理解还行：
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<queue> #include<deque> #include<stack> #include<vector> #include<cmath> #include<ctime> #include<algorithm> #include<set> #include<map> #include<bitset> #include<iomanip> #include<cctype> #define sum(p) w[p].sum #define l(p) w[p].l #define r(p) w[p].r #define add(p) w[p].add #define ll long long using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return f>0?x:-x; } const int MAXN=200010; int n,m,top,cnt,id,p1,p2; int a[MAXN],l[MAXN],r[MAXN]; int s[MAXN],root[MAXN]; struct wy { int p,l,r; int v; int friend operator <(wy a,wy b) { return a.p<b.p; } }t[MAXN<<2]; struct wx { int l,r; ll sum; ll add;//标记永久化 }w[MAXN<<6]; inline void change(int &p,int last,int l,int r,int L,int R,int v) { p=++id;w[p]=w[last]; sum(p)+=v*(R-L+1); if(L==l&&R==r){add(p)+=v;return;} int mid=(l+r)>>1; if(L>mid)change(r(p),r(last),mid+1,r,L,R,v); else { if(R<=mid)change(l(p),l(last),l,mid,L,R,v); else { change(l(p),l(last),l,mid,L,mid,v); change(r(p),r(last),mid+1,r,mid+1,R,v); } } } inline ll ask(int s1,int s2,int l,int r,int L,int R) { if(L==l&&R==r)return sum(s2)-sum(s1); int mid=(l+r)>>1; ll cnt=(R-L+1)*(add(s2)-add(s1)); if(L>mid)return ask(r(s1),r(s2),mid+1,r,L,R)+cnt; else { if(R<=mid)return ask(l(s1),l(s2),l,mid,L,R)+cnt; else { return ask(l(s1),l(s2),l,mid,L,mid)+ask(r(s1),r(s2),mid+1,r,mid+1,R)+cnt; } } } int main() { freopen("1.in","r",stdin); n=read();m=read();p1=read();p2=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<=n;++i) { while(top&&a[s[top]]<=a[i])--top; s[++top]=i;l[i]=s[top-1]; } top=0; for(int i=n;i>=1;--i) { while(top&&a[s[top]]<=a[i])--top; s[++top]=i;r[i]=s[top-1]; } //for(int i=1;i<=n;++i)printf("%d %d ",l[i],r[i]); for(int i=1;i<=n;++i)//对于每个i贡献都是若干个区间 { if(l[i]&&r[i])t[++cnt]=(wy){l[i],r[i],r[i],p1}; if(l[i])t[++cnt]=(wy){l[i],i+1,r[i]==0?n:r[i]-1,p2}; if(r[i])t[++cnt]=(wy){r[i],l[i]==0?1:l[i]+1,i-1,p2}; if(i+1<=n)t[++cnt]=(wy){i,i+1,i+1,p1}; } sort(t+1,t+1+cnt); //for(int i=1;i<=cnt;++i)printf("%d %d %d %d ",t[i].p,t[i].l,t[i].r,t[i].v); for(int i=1,j=1;i<=n;++i) { root[i]=root[i-1]; while(j<=cnt&&t[j].p==i) { if(t[j].l<=t[j].r)change(root[i],root[i],1,n,t[j].l,t[j].r,t[j].v); ++j; } } for(int i=1;i<=m;++i) { int x,y; x=read();y=read(); printf("%lld ",ask(root[x-1],root[y],1,n,x,y)); } return 0; }
下一道 乌拉：
LINK：Count 什么时候我才能无忧无虑的在星空之下数星星啊...以前很喜欢看桐华的书 接其书名一用 那片星空那片海。
这道题的大体上和上面的那一道题是一样的，对于一个点对要么 i=j-1要么 设c为 i+1<=k<=j-1 max{ak} c<min(ai,aj);
wa 双倍经验 比上一题少了一个条件...分析每个点对答案的贡献然后发现阵型为矩形 然后直接主席树前缀和 而且这个做法还是预处理之后强制在线的呢!
但是obviously 这个是单点修改了没必要区间标记永久化了少了一个tag 更好写一点...对于有重复的数字的出现 在某个区间之内两个重复的数字会对同一个区间进行答案的贡献 此时应该排除一些点的干扰 考虑在一个大区间内对于一个相同的数字我们随机指定一个为master
此外其他的点将不会被造成贡献 最巧的方法自然是求每个点的最左端比起大的数字每个点最优端比其大的数字 求每个点最左端>=其的数字 当这个和刚刚那个重合的时候就是答案了或者说当这个数字不等于当前数字就能使用了因为他是当前区间的第一个呢...
注意第二个 i i-1的贡献可以不插到主席树中减小一倍常数可直接输出...
//#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<utility> #include<queue> #include<deque> #include<stack> #include<vector> #include<cmath> #include<ctime> #include<algorithm> #include<set> #include<map> #include<bitset> #include<iomanip> #include<cctype> #define sum(p) w[p].sum #define l(p) w[p].l #define r(p) w[p].r #define add(p) w[p].add #define ll long long #define min(x,y) ((x)>(y)?(y):(x)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; char *fs,*ft,buf[1<<15]; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return f>0?x:-x; } const int MAXN=300010; int n,m,top,cnt,id,T,ans; int a[MAXN],l[MAXN],r[MAXN],v[MAXN]; int s[MAXN],root[MAXN]; struct wy { int p,x; int friend operator <(wy a,wy b){return a.p<b.p;} }t[MAXN]; struct wx { int l,r; int sum; }w[MAXN*20]; inline void change(int &p,int last,int l,int r,int x,int v) { p=++id;w[p]=w[last]; if(l==r){sum(p)+=v;return;} int mid=(l+r)>>1; if(x<=mid)change(l(p),l(last),l,mid,x,v); else change(r(p),r(last),mid+1,r,x,v); sum(p)=sum(l(p))+sum(r(p)); } inline int ask(int s1,int s2,int l,int r,int L,int R) { if(L<=l&&R>=r)return sum(s2)-sum(s1); int mid=(l+r)>>1; int cnt=0; if(L<=mid)cnt+=ask(l(s1),l(s2),l,mid,L,R); if(R>mid)cnt+=ask(r(s1),r(s2),mid+1,r,L,R); return cnt; } int main() { //freopen("1.in","r",stdin); n=read();m=read();T=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=1;i<=n;++i) { while(top&&a[s[top]]<=a[i])--top; s[++top]=i;l[i]=s[top-1]; } top=0; for(int i=n;i>=1;--i) { while(top&&a[s[top]]<=a[i])--top; s[++top]=i;r[i]=s[top-1]; } top=0; for(int i=1;i<=n;++i) { while(top&&a[s[top]]<a[i])--top; s[++top]=i;v[i]=s[top-1]; } for(int i=1;i<=n;++i) if(l[i]&&r[i]&&l[i]==v[i])t[++cnt]=(wy){l[i],r[i]}; sort(t+1,t+1+cnt); for(int i=1,j=1;i<=n;++i) { root[i]=root[i-1]; while(j<=cnt&&t[j].p==i) { change(root[i],root[i],1,n,t[j].x,1); ++j; } } for(int i=1;i<=m;++i) { int x,y; x=read();y=read(); if(T) { int u=(x+ans-1)%n+1; int v=(y+ans-1)%n+1; x=min(u,v);y=max(u,v); } printf("%d ",(ans=(ask(root[x-1],root[y],1,n,x,y)+y-x))); } return 0; }
下一道 乌拉：
最大子矩阵 悬线法？我不会...怎么办呢>>>这个也是单调栈的经典应用 可以考虑枚举左上方的点和又下方的点然后判断形成的矩阵是否是合法的 从中取max 复杂度n^6 前缀和一下n^4好像不太行...这是这个算法的最低复杂度了。
考虑怎么办呢...一个比较 基础的预处理是 这个点能向上延伸多大就尽量是多大所以可以先预处理出向上的延伸的最大值 我们此时考虑枚举这个矩阵的下面两个点 形成的矩阵合法当且仅当 他们之间向上延伸的最大距离取min。
这就迎来了一个和影魔类似的思路了考虑每个点对答案的贡献 如果有贡献那么这个点能向上延伸的长度就是最小的 考虑单调栈就出这个点能像左延伸最远到哪 当然这个范围是处在当前点是最小的基础之上 同理对右边也做一遍。
这样我们针对每一个点都有一个这样的东西统计答案就好了 是最优的么 显然我们是把所有最优的情况便利到了(首先是每一个点 在一个以这个点为基础的最大矩阵面积故一定是最优的。
复杂度 n^2;
//#include<bits/stdc++.h> #include<iostream> #include<cmath> #include<ctime> #include<algorithm> #include<cctype> #include<utility> #include<queue> #include<map> #include<set> #include<bitset> #include<deque> #include<vector> #include<cstdio> #include<cstdlib> #include<iomanip> #include<stack> #include<string> #include<cstring> #define INF 1000000000 #define ll long long #define db double #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)>(y)?(y):(x)) using namespace std; char buf[1<<15],*fs,*ft; inline char getc() { return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++; } inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } const int MAXN=1010; int n,m,top,ans; char ch; int a[MAXN][MAXN]; int l[MAXN],r[MAXN],s[MAXN]; int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<=n;++i) { for(int j=1;j<=m;++j) { ch=getc(); while(ch!='R'&&ch!='F')ch=getc(); if(ch=='F')a[i][j]=a[i-1][j]+1; } top=0;s[0]=0; for(int j=1;j<=m;++j)//寻找向左延伸的最远距离 { while(top&&a[i][j]<=a[i][s[top]])--top; l[j]=s[top]+1;s[++top]=j; } top=0;s[0]=m+1; for(int j=m;j>=1;--j) { while(top&&a[i][j]<=a[i][s[top]])--top; r[j]=s[top]-1;s[++top]=j; } for(int j=1;j<=m;++j)ans=max(ans,(r[j]-l[j]+1)*a[i][j]); } printf("%d ",ans*3); return 0; }
其实归根结底 都是栈的性质以及单调栈的性质...