初心者 Golfer 的自我修养

· · 题解

能不写成答辩题的题就不要用答辩做法！！1

想起来补了 z 宝模拟赛，JOI22 本选去掉第一题组成提高组模拟赛（

官方题解里有个特别抽象的图，实际上感觉不用那么多 case 啊。

intro：小课题 1 扫过去，找大于小于号连续段。小课题 2 枚举矩形按值排序，观察在值上相邻的格子在原位置上是否相邻。

同样考虑走的路径，发现在走链的路径的过程中，恰好有一个点没有入度，一个点没有出度，其他点都是出度为一，入度为一，这个和官方题解是一样的。

而且在确定了当前矩形边界的情况下，可以发现它只可能走四周比它小的最大格子，这个可以通过小课题 2 的暴力 O(n^2m^2\log(nm)) 做法得出。

有了上面两个结论以后，在确定了当前矩形边界的情况下，我们把一个格子 (i,j) 的权 v_{i,j} 定义为：

记 l 表示 (i,j) 四周比 A_{i,j} 小的最大值（没有就记为 0），r 为 (i,j) 四周比这个格子权大的最小值（没有就记为 X，表示一个充分大的值），那么 v_{i,j}=\operatorname{R}(r<X,A_{i,j},X)-l。其中 \operatorname{R}(P,x,y) 表示条件 P 为真时值为 x，否则为 y。

根据上面的结论，一条合法路径上所有格子的权值和应该是 X。（在链上的非端点都抵掉了，链尾剩下个 0，链头贡献 X）

后面就是转棋盘，枚举上下行的范围，然后扫过去，问题变成了满足左右列之间格子权值和为 X 的对数，这个可以差分后 O(m\log m) 解决。

剩下的部分是枚举长或宽为一的矩阵，这个在小课题 1 里已经解决。

总时间复杂度 O((nm)^{1.5}\log m)。

求 v_{i,j} 的时候需要做五次前缀和，枚举左右列的时候根据靠边情况权值需要拆成六部分，别的应该没什么难写的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int const N=400010,X=500000000000ll,dx[]={0,-1,1,0},dy[]={-1,0,0,1};
int n,m,ans;
vector<vector<int> >a,l,r,u,d,s;
void init(vector<vector<int> >&a){
    a.resize(n+2);
    for(int i=0;i<=n+1;i++)
        a[i].resize(m+2);
}
int calc(int x,int y,int s){
    int l=0,r=X;
    for(int i=0;i<4;i++)
        if(s>>i&1){
            int tx=x+dx[i],ty=y+dy[i];
            if(tx<1||ty<1||tx>n||ty>m)
                continue;
            if(a[tx][ty]>a[x][y])
                r=min(r,a[tx][ty]);
            else l=max(l,a[tx][ty]);
        }
    return(r<X?a[x][y]:X)-l;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m,ans=n*m;
    if(n>m){
        swap(n,m),init(a);
        for(int j=1;j<=m;j++)
            for(int i=1;i<=n;i++)
                cin>>a[i][j];
    }else{
        init(a);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
    }
    init(l),init(r),init(u),init(d),init(s);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            l[i][j]=l[i-1][j]+calc(i,j,14),
            r[i][j]=r[i-1][j]+calc(i,j,7),
            u[i][j]=u[i][j-1]+calc(i,j,13),
            d[i][j]=d[i][j-1]+calc(i,j,11),
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+calc(i,j,15);
    for(int pl=1;pl<=n;pl++)
        for(int pr=pl+1;pr<=n;pr++){
            map<int,int>f;
            for(int i=1;i<=m;i++){
                ans+=f[X-r[pr-1][i]+r[pl][i]-u[pl][i-1]-d[pr][i-1]-s[pr-1][i-1]+s[pl][i-1]-calc(pl,i,5)-calc(pr,i,3)];
                f[l[pr-1][i]-l[pl][i]-u[pl][i]-d[pr][i]-s[pr-1][i]+s[pl][i]+calc(pl,i,12)+calc(pr,i,10)]++;
            }
        }
    for(int i=1;i<=n;i++)
        for(int t=1,j=2;j<=m;j++)
            if(t++,j==m||(a[i][j]-a[i][j-1])*(a[i][j+1]-a[i][j])<0)
                ans+=t*(t-1)/2,t=1;
    for(int j=1;j<=m;j++)
        for(int t=1,i=2;i<=n;i++)
            if(t++,i==n||(a[i][j]-a[i-1][j])*(a[i+1][j]-a[i][j])<0)
                ans+=t*(t-1)/2,t=1;
    cout<<ans<<"\n";
}