题解：CF2227E It All Went Sideways

I_do_Cpp · 2026-05-12 20:43:49 · 题解

前言

本来不会的来着，看到其他题解单调栈三个字突然醒悟。

前置知识

单调栈

题目解析

我们定义横着数称为行，竖着数称为列。

容易注意到方块移动当且仅当 A_(i-1) < A_i，这玩意用单调栈维护非常合适，是一个栈顶小的栈。

每次弹出计算代价时，设 l_i 表示满足 0< j<i 且 A_j<A_i 的最大 j。特别的，若不存在，则 l_i 为 0。则 A_{k} 弹出 A_i 时（1 \le i < n），则本次移动了从位置 l_i+1 到 i，高度为 A_k-A_i 的长方形。

下面是证明和细节：

• 不会漏算：显然这些方块从来没移动，因为 A_i 是区间 ({l_i},i] 最小的，在区间中高度为 [A_i,A_k] 之间这些格子没动过。
• 不会多算：单调栈计算完这些高度后会立刻弹出，不会参与后续计算
• 等于的情况：因为我们的 l_i 不考虑等于情况，每次计算区间 ({l_i},i] 会包含等于的值，为了不重复计算，我们在等于时也弹出。

对于移除一个放格如何令答案更大，考虑在单调栈最终剩下的所有数字，移除格子的下标 i 一定可以让第 A_i 行的区间区间 (l_i,i] 移动。显然第 A_i 行 l_i 到 i 不存在缺失的数字，否则一定会有 k 满足 l_i<j<i 且 A_i>A_j 的 j，那么 l_i 应该为 j，所以不会出现这种情况。

别忘记答案减去 1。显然计算移除一个放格如何令答案更大时最少有 1 的代价，完美避开导致一次还没有效果并且让移动格数 -1 的情况。

复杂度是线性的，因为只用到了单调栈。

正解代码

跑的飞快。

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,a[200005]={0},ans=0;
        int l[200005]={0};
        stack<int> stk;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=n;i>=1;i--)
        {
            while(!stk.empty() && a[stk.top()]>a[i]) 
            {
                l[stk.top()]=i;
                stk.pop();
            }
            stk.push(i);
        }
        while(!stk.empty())
        {
            l[stk.top()]=0;
            stk.pop();
        }
        //for(int i=1;i<=n;i++) cout<<l[i]<<" ";
        int res=0,num=INT_MAX;
        for(int i=1;i<=n;i++)
        {
            while(!stk.empty() && a[stk.top()]>=a[i]) 
            {
                int b=stk.top();
                ans+=(b-l[b])*(a[b]-a[i]);
                stk.pop();
            }
            stk.push(i);
        }
        while(!stk.empty())
        {
            int b=stk.top();
            res=max(res,b-l[b]);
            num=min(num,b);
            stk.pop();
        }
        cout<<ans+res-1<<"\n";
    }
    return 0;
}