ZR 集训 Day3 – 基础分块算法与离线算法

ooliver 发布于 1 天前 109 次阅读 OI

AI 摘要

从 m=2 的平凡公式，到 m=3 的二维偏序与树状数组，再到 m=4 时仅靠一次容斥便化繁为简——你将看到如何用短短几行离线统计，优雅地斩获 NOI Online 高分。

ZR 集训 Day3 - 基础分块算法与离线算法

P8253 [NOI Online 2022 提高组] 如何正确地排序 - 洛谷

1. $m=2$

显然 $f(i,j)=\min\limits_{k=1}^2(a_{k,i}+a_{k,j})+\max\limits_{k=1}^2(a_{k,i}+a_{k,j})=a_{1,i}+a_{1,j}+a_{2,i}+a_{2,j}$，

那答案就会等于 $\sum\limits_{i=1}^n\sum\limits_{j=1}^nf(i,j)=2n\sum\limits_{i=1}^2\sum\limits_{j=1}^n a_{i,j}$。

2. $m=3$

先考虑最大值，最小值可以取反后再求一遍最大值。

我们假设 $a_{1,i}+a_{1,j}$ 是最大的，就有两个关系：

$a_{1,i}+a_{1,j}>a_{2,i}+a_{2,j} \rightarrow a_{1,i}-a_{2,i}>-(a_{1,j}-a_{2,j})$

$a_{1,i}+a_{1,j}>a_{3,i}+a_{3,j} \rightarrow a_{1,i}-a_{3,i}>-(a_{1,j}-a_{3,j})$

得到两个偏序关系后，就变成了二维偏序问题，直接排序+BIT 即可。

3. $m=4$

不难发现，我们枚举四行中每三行并用 $m=3$ 的方法统计，把答案加一起会发现一共统计了 3 次最值和 1 次次值，所以减去一个 $m=2$ 时的答案再除以二就行了。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lowbit(x) x&-x
const int N=2e5+5;

int n,m,sum;
int a[5][N];

struct node{
    int x,y,id;
    bool operator<(const node b)const{
        return x<b.x;
    }
}b[N];

struct pt{
    int u,v;
    bool operator<(const pt b)const{
        return u>b.u;
    }
}p[N];

struct qr{
    int q,w,id;
    bool operator<(const qr b)const{
        return q>b.q;
    }
}q[N];

struct BIT{
    int tr[N<<1];
    void add(int pos,int k){
        while(pos<(N<<1)){
            tr[pos]+=k;
            pos+=lowbit(pos);
        }
    }
    int check(int pos){
        if(!pos) return 0;
        int res=0;
        while(pos>0){
            res+=tr[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
}bit;

int solve(int x,int y,int z){
    int res=0;
    for(int i=1;i<=n;i++){
        p[i]={a[x][i]-a[y][i],a[x][i]-a[z][i]};
        q[i]={-p[i].u,-p[i].v,i};
    }
    sort(p+1,p+n+1);
    sort(q+1,q+n+1);
    int su=(x<y)?1:0,sv=(x<z)?1:0;
    int i=1,tot=0;
    for(int j=1;j<=n;j++){
        while(i<=n&&(su?p[i].u>q[j].q:p[i].u>=q[j].q)){
            bit.add(p[i].v+N,1);
            tot++,i++;
        }
        int t=q[j].w;
        int les=bit.check(t+N-!sv);
        res+=(tot-les)*a[x][q[j].id];
    }
    for(int k=1;k<i;k++) bit.add(p[k].v+N,-1);
    return res;
}

signed main(){
    int ans=0;
    cin>>m>>n;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) cin>>a[i][j],sum+=a[i][j];
    if(m==2) cout<<2*n*sum;
    else if(m==3){
        ans+=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)<<1);
        for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) a[i][j]=-a[i][j];
        ans-=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)<<1);
        cout<<ans;
    }
    else{
        ans+=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)+
            solve(1,2,4)+solve(2,1,4)+solve(4,1,2)+
            solve(1,3,4)+solve(3,1,4)+solve(4,1,3)+
            solve(2,3,4)+solve(3,2,4)+solve(4,2,3)<<1);
        for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) a[i][j]=-a[i][j];
        ans-=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)+
            solve(1,2,4)+solve(2,1,4)+solve(4,1,2)+
            solve(1,3,4)+solve(3,1,4)+solve(4,1,3)+
            solve(2,3,4)+solve(3,2,4)+solve(4,2,3)<<1);
        cout<<(ans-sum*2*n>>1);
    }
    return 0;
}