题解AT2289 [ARC067D] Yakiniku Restaurants

· · 题解

挺妙的一道题，感觉也不是很难但想了很久没想出来。

首先，我们选的必然是一个连续的线段，不然把中间的点选上一定不会变劣。

由于发现 m 个物体其实是独立的，我们把考虑 m 个物品分开来，对每个物品维护其在左边第一个比他大的位置 L_i ，右边第一个大于等于他的位置 R_i ，这个可以用单调栈来维护。那么起点为 [L_i+1,i] ，终点为 [i,R_i-1] 的线段对于这种物品的答案，一定是算这个位置的贡献。我们直接用二维差分统计即可。

注意一边取大于，另一边要取大于等于，不然会漏算。

复杂度 O(n^2+nm)

代码如下

// Problem: AT2289 [ARC067D] Yakiniku Restaurants
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT2289
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 2022-06-02 14:36:35
// Author : louhao088

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define lowbit(x) (x&-x)
#define int long long
const int maxn=5e3+5,M=34005;
inline int read(){
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
inline void print(int x){
    static int a[55];int top=0;
    if(x<0) putchar('-'),x=-x;
    do{a[top++]=x%10,x/=10;}while(x);
    while(top) putchar(a[--top]+48);
}
int n,m,b[maxn],s[maxn][maxn],a[205][maxn],l[maxn],r[maxn],st[maxn],ans=0;
void add(int x,int y,int x2,int y2,int num){
    s[x][y]+=num;s[x2+1][y2+1]+=num;
    s[x2+1][y]-=num;s[x][y2+1]-=num;
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read();memset(s,0,sizeof s);
    for(int i=2;i<=n;i++)b[i]=b[i-1]+read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)a[j][i]=read();
    for(int i=1;i<=m;i++){
        memset(l,0,sizeof l);memset(r,0,sizeof r);int top=0;
        for(int j=1;j<=n;j++){
            while(top>0&&a[i][st[top]]<a[i][j])top--;
            l[j]=st[top];st[++top]=j;
        }
        top=1,st[top]=n+1;
        for(int j=n;j>=1;j--){
            while(top>1&&a[i][st[top]]<=a[i][j])top--;
            r[j]=st[top];st[++top]=j;
            add(l[j]+1,j,j,r[j]-1,a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            s[i][j]+=s[i][j-1]+s[i-1][j]-s[i-1][j-1];
            if(i>j)continue;
            ans=max(s[i][j]-b[j]+b[i],ans);
        }
    cout<<ans<<endl;
    return 0;
}