感觉不错 Feel Good 和 长方形（单调栈的应用）
题目描述
给出正整数 \(n\) 和一个长度为 \(n\) 的数列 \(a\)，要求找出一个子区间 \([l,r]\)，使这个子区间的数字和乘上子区间中的最小值最大。
形式化的，要求找出 \([l,r]\) 使得：
\[\left(\sum \limits_{i=l}^{r}a_i\right)\times\min\limits_{i=l}^{r}a_i \]最大。输出这个最大值与区间的两个端点。
在答案相等的情况下最小化区间长度，最小化长度的情况下最小化左端点序号。
数据范围
\(1 \leq n \leq 10^5, 0 \leq a_i \leq 10^6\)。
解法
想到单调栈可以求一个元素作为极值的最大区间，那么我们用单调栈处理出对于每一个元素，它作为最小值的最左边和最右边。处理完毕后做一遍前缀和，然后遍历每个元素，\(O(1)\)查询答案取\(max\)即可。
感觉到这题典中典，同时要注意单调栈这玩意在计算几何中好像很常用。
代码实现
int n;
void solve(){
vector<int>a(n+1);
vector<int>l(n+1);vector<int>r(n+1);
stack<pair<int,pii>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
int lt=i;
while(!t.empty()&&t.top().fi>a[i]){
auto temp=t.top();
t.pop();
r[temp.se.fi]=i-1;
lt=temp.se.se;
}
l[i]=lt;
t.push({a[i],{i,lt}});
}
while(!t.empty()){
auto temp=t.top();
t.pop();
r[temp.se.fi]=n;
}
vector<int>s(n+1);
for(int i=1;i<=n;i++)s[i]=a[i]+s[i-1];
ll ans=0,ansl=1,ansr=1;
for(int i=1;i<=n;i++){
ll temp=1ll*a[i]*(s[r[i]]-s[l[i]-1]);
if(temp>ans){
ans=temp;ansl=l[i];ansr=r[i];
}
else if(temp==ans&&ansr-ansl>r[i]-l[i]){
ans=temp;ansl=l[i];ansr=r[i];
}
else if(temp==ans&&ansr+l[i]==ansl+r[i]&&ansl>l[i]){
ans=temp;ansl=l[i];ansr=r[i];
}
}
cout<<ans<<"\n";
cout<<ansl<<" "<<ansr<<"\n";
}
然后我们看下一题
长方形
题目描述
小明今天突发奇想，想从一张用过的纸中剪出一个长方形。
为了简化问题，小明做出如下规定：
（1）这张纸的长宽分别为 \(n,m\)。小明将这张纸看成是由\(n\times m\)个格子组成，在剪的时候，只能沿着格子的边缘剪。
（2）这张纸有些地方小明以前在上面画过，剪出来的长方形不能含有以前画过的地方。
（3）剪出来的长方形的大小没有限制。
小明看着这张纸，想了好多种剪的方法，可是到底有几种呢？小明数不过来，你能帮帮他吗？
数据范围
\(1\leq n\leq 1000,1\leq m\leq 1000\)
解法
我们首先处理出对于每一个格子，以它为低，向上连续最多有多少个没有画过的地方，记为h，然后用单调栈，去处理其作为最大值的区间右端点，和其作为唯一最大值的区间左端点。
这里为什么不能像上一道题一样直接算呢？因为其计算的是数量，而不是最大长方形面积。
为什么对于左端点要求其为唯一最大值呢？如果不唯一的话，当出现连续的相同数h时，必然会算重。
处理完这些后，累加左边长度乘右边长度乘高度，即为答案。
之前看到这个解法后，真心不知道咋做出来的。后来了解到这其实就是一种叫悬线法的trick。
代码实现
int op[1010][1010];
int h[1010][1010];
int l[1010][1010];
int r[1010][1010];
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char c;cin>>c;
op[i][j]=(c=='.');
}
}
for(int i=1;i<=m;i++){
int last=0;
for(int j=1;j<=n;j++){
if(op[j][i])h[j][i]=j-last;
else last=j;
}
}
for(int k=1;k<=n;k++){
stack<pii>t;
for(int i=1;i<=m;i++){
while(!t.empty()&&t.top().fi>h[k][i]){
r[k][t.top().se]=i-1;
t.pop();
}
t.push({h[k][i],i});
}
while(!t.empty()){
r[k][t.top().se]=m;
t.pop();
}
}
for(int k=1;k<=n;k++){
stack<pii>t;
for(int i=m;i>=1;i--){
while(!t.empty()&&t.top().fi>=h[k][i]){
l[k][t.top().se]=i+1;
t.pop();
}
t.push({h[k][i],i});
}
while(!t.empty()){
l[k][t.top().se]=1;
t.pop();
}
}
ll ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=h[i][j]*(r[i][j]-j+1)*(j-l[i][j]+1);
}
}
cout<<ans<<"\n";
}