题解：P15173 [SWERC 2021] Drone Photo

gdxsbgx · 2026-06-06 18:09:08 · 题解

妙妙题。

这里主要讲一下思考过程，当然如果你是脑电波大手子那就当我啥也没说。

首先容易想到的是枚举最大的两个数构成的边，可以做到 O(n^3) ，但没什么前途。

我们转而考虑对角线。这时我们发现对于一个矩形上的点，它比它所对的对角线上的两个点权值都小的结构在合法矩形中出现 1 次，不合法矩形中出现 2 次，这启发我们统计这个结构的数量。

到这里，我们就可以发现对角线相比对边的好处：对于一个点，我们枚举它所对对角线时对角线上的两个点时独立的，对边则不然。 利用这条性质，我们统计出一个点在其所在行和列上的排名即可算出结构的数量，进而计算最终答案。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3fll

const int N=2e3+10;

ll a[N][N],s1[N][N],s2[N][N],b[N],id[N],n;

bool cmp(int x,int y){return b[x]<b[y];}

inline void Solve()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >> a[i][j];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++) id[j]=j,b[j]=a[i][j];
        sort(id+1,id+n+1,cmp);
        for(int j=1;j<=n;j++) s1[i][id[j]]=j-1;
    }
    for(int j=1;j<=n;j++)
    {
        for(int i=1;i<=n;i++) id[i]=i,b[i]=a[i][j];
        sort(id+1,id+n+1,cmp);
        for(int i=1;i<=n;i++) s2[id[i]][j]=i-1;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            ans+=s1[i][j]*s2[i][j];
    ans=n*n*(n-1)*(n-1)/2-ans;
    cout << ans << '\n';
}

int main()
{
    // int t=clock();
    // freopen("gdx.in","r",stdin);
    // freopen("gdx.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // init();
    // int Type;
    // cin >> Type;
    // int T;
    // cin >> T;
    // while(T--)
    Solve();
    // cout << clock()-t << '\n';
    return 0;
}