题解 P8253 【[NOI Online 2022 提高组] 如何正确地排序】

enucai · 2022-04-02 18:33:07 · 题解

Preface

二维偏序解法。来一篇代码简单一点的题解，代码长度 1.12 KB。

Analysis

正难则反。我们很难正向计算每个数的贡献（三维偏序），那么我们假设所有数对 \max 和 \min 都有贡献，则答案为 2n\times sum，这个很容易计算。

接下来我们要减去没有对 \max 产生贡献的与没有对 \min 产生贡献的数。假设现在有三个数组 A,B,C。我们要算对于 B 中的每一个数 B_i，有多少个 j 满足一下条件：

移项一下，得：

这是一个二维偏序问题，可以 O(n\log n) 解决。

所以我们只要枚举任意有序的三个数组，进行上述算法即可算出所有不合法的数的总和，减去即可。时间复杂度 O(n\log n)，带一个 24 的常数。

需要注意的是，可能有相等的数，执行上述算法两者都会被减去，因此强制规定：若两个数相同，编号小的数组中的元素 < 编号大的数组中的元素。

Code

Talk is cheap, show me the code.

奉上极简代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,j,k) for(int i=(j);i<=(k);i++)
#define Rof(i,j,k) for(int i=(j);i>=(k);i--)
#define N 200010
#define base 200001
int n,m,a[4][N],ans=0,c[2*N],tot;
struct que{
    int op,x,y,val;
    bool operator<(const que &p)const{
        if(x!=p.x) return x<p.x;
        return op<p.op;
    }
}q[400010];
void upd(int x){
    while(x<2*base) c[x]++,x+=x&(-x);
}
int qry(int x){
    int res=0;
    while(x) res+=c[x],x-=x&(-x);
    return res;
}
int calc(int x,int y,int z){
    int res=0;
    memset(c,0,sizeof(c)),tot=0;
    For(i,1,n){
        q[++tot]=(que){0ll,a[x][i]-a[y][i]+(x>y),a[y][i]-a[z][i]+(y>z),0ll};
        q[++tot]=(que){1ll,a[y][i]-a[x][i],a[z][i]-a[y][i],a[y][i]};
    }
    sort(q+1,q+tot+1);
    For(i,1,tot){
        if(q[i].op==0) upd(q[i].y+base);
        else res+=q[i].val*qry(q[i].y+base);
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>m>>n;
    For(i,0,m-1) For(j,1,n) cin>>a[i][j];
    For(i,m,3) For(j,1,n) a[i][j]=a[i-m][j];
    For(i,0,3) For(j,1,n) ans+=2*n*a[i][j];
    For(i,0,3) For(j,0,3) For(k,0,3) if(i!=j&&j!=k&&k!=i) ans-=calc(i,j,k);
    cout<<ans;
}