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 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; }`
ZR 集训 Day3 - 基础分块算法与离线算法
笔记