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

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

1. $m=2$

显然 $f(i,j)=\min {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{k=1}^2}(a_{k,i}+a_{k,j})+\max {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{k=1}^2}(a_{k,i}+a_{k,j})=a_{1,i}+a_{1,j}+a_{2,i}+a_{2,j}$，

那答案就会等于 $\sum {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{i=1}^n}\sum {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{j=1}^n}f(i,j)=2n\sum {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{i=1}^2}\sum {\text{[PARSE ERROR: Undefined("Command("limits")")]}}_{{j=1}^n}{a}_{i,j}$。

2. $m=3$

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

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

$a_{1,i}+a_{1,j}\text{[PARSE ERROR: Ampersand]}gt;a_{2,i}+a_{2,j}\to a_{1,i}-a_{2,i}\text{[PARSE ERROR: Ampersand]}gt;-(a_{1,j}-a_{2,j})$

$a_{1,i}+a_{1,j}\text{[PARSE ERROR: Ampersand]}gt;a_{3,i}+a_{3,j}\to a_{1,i}-a_{3,i}\text{[PARSE ERROR: Ampersand]}gt;-(a_{1,j}-a_{3,j})$

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

3. $m=4$

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

代码：

C++

#include
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 operatorb.u;
    }
}p[N];

struct qr{
    int q,w,id;
    bool operatorb.q;
    }
}q[N];

struct BIT{
    int tr[N0){
            res+=tr[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
}bit;

int solve(int x,int y,int z){
    int res=0;
    for(int i=1;iq[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>m>>n;
    for(int i=1;i>a[i][j],sum+=a[i][j];
    if(m==2) cout>1);
    }
    return 0;
}

`#include
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 operatorconst node b)const{
        return xb.x;
    }
}b[N];

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

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

struct BIT{
    int tr[N1];
    void add(int pos,int k){
        while(pos(N1)){
            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;in;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=(xy)?1:0,sv=(xz)?1:0;
    int i=1,tot=0;
    for(int j=1;jn;j++){
        while(in&&(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;ki;k++) bit.add(p[k].v+N,-1);
    return res;
}

signed main(){
    int ans=0;
    cin>>m>>n;
    for(int i=1;im;i++) for(int j=1;jn;j++) cin>>a[i][j],sum+=a[i][j];
    if(m==2) cout2*n*sum;
    else if(m==3){
        ans+=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)1);
        for(int i=1;im;i++) for(int j=1;jn;j++) a[i][j]=-a[i][j];
        ans-=(solve(1,2,3)+solve(2,1,3)+solve(3,1,2)1);
        coutans;
    }
    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;im;i++) for(int j=1;jn;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;
}`