P9120
Kazemaru
·
·
题解
P9120
大意
给定 k \times n 的二维数组，你可以任意次让任意一列循环位移，求最后每行极差的最大值最小是多少。
思路
最大值最小，二分最大的极差，并把整个数组的最大值换到第一行。
记整个数组的最大值为 $X$，最小值为 $Y$，二分的值为 $C$，值域为 $V$。
$k=2$ 时，最小值一定在第二行（在第一行时不影响），第一行的取值范围是 $[X-C,X]$，第二行的取值范围是 $[Y,Y+C]$。
$k=3$ 时，枚举最小值在哪一行，同样可以确定两行的取值范围。
枚举每一列如何循环位移，找出对于剩下那一行，每一列可以取哪些值。
问题变为是否有一个长度为 $C$ 的区间使得每一列有至少一种取值在里面。
顺序枚举最靠右在里面的点，注意不要写成 $\mathcal{O}(V)$。
$k=4$ 时，类比上面做法，枚举最小值在哪一行，每一列 $i$ 记录若干个数对 $(x,y)$ 表示第一行（未确定取值范围的行，下同）和第二行分别可以取的值。
问题变为是否有一个边长为 $C$ 的正方形覆盖每一列的点（数对）至少一次。
再进行一下转化，把每个数对变为以其为左下角边长为 $C$ 颜色为 $i$ 的正方形，是否有一个点同时被所有颜色的正方形覆盖（该点相当于原问题正方形的右上角）。
只有 $m$ 种不同的循环位移，则每列（每种颜色）最多 $m$ 个正方形。
先通过容斥把所有相同颜色的正方形的并用若干个矩形的和差表示，将同颜色的并里面点值都加 $1$，求是否有位置等于 $n$。
用扫描线维护这个平面（后有详细做法），每次更改时看最大值是否为 $n$。
此做法复杂度为 $\mathcal{O}(2^kn\log n\log V) $，需要非常优秀的常数，我乱来，理论能过。
在扫描线对于一行修改时可以差分把区间改拆成前缀改，保证相同的只用数据结构改一次，这样容斥得到的 $2^k$ 个矩形会变为 $\mathcal{O}(k)$ 个不同的前缀改，同时减少线段树常数。
若是还过不去，发现正方形的数量和 $C$ 正相关，即 $C$ 越大每次判断时间越多，尝试调整二分（比如前几次每次跳 $\frac34$ 处）。
------------
#### 扫描线
$N$ 次将一个矩形内所有整点加 $w_i$，并求最后全局最大值是否等于 $n$。
枚举矩形**边缘**的 $y$ 坐标，每个矩形看成在上边界被扫到前区间加 $w_i$，在下边界被扫到后区间减 $w_i$。
一整行所有区间加算完后求全局最大值，线段树维护即可。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
// #define int long longs
#define f(i,j,k) for(register int i=j;i<=k;++i)
#define g(i,j,k) for(register int i=j;i>=k;--i)
int n,m,s,l;
const int N=3e5+7;
int a[N][5],b[N],c[N],d[N],u[N],v[N];
int o,p,q,r,tot,cnt,all,ex,xx,yy,zz;
vector<int>xw[N];
struct Dusk{
struct xds{
int l,r,c,t;
}a[N];
void bt(int id,int l,int r){
a[id]=(xds){l,r,0,0};
if(l<r)bt(id<<1,l,(l+r)/2),bt(id<<1|1,(l+r)/2+1,r);
}
void add(int id,const register int&r,const register int&c){
if(a[id].r<=r)return a[id].c+=c,a[id].t+=c,void();
if(a[id<<1].r<r)add(id<<1|1,r,c);add(id<<1,r,c);
a[id].c=max(a[id<<1].c,a[id<<1|1].c)+a[id].t;
}
}T;
struct Flametail{
int a,b,c,d;
inline bool operator<(const Flametail&y)const{return c==y.c?d<y.d:c<y.c;}
inline Flametail operator*(const Flametail&y)const{return (Flametail){max(a,y.a),min(b,y.b),max(c,y.c),min(d,y.d)};}
}ls;
vector<Flametail>e[N],f[N];
const Flametail ____=(Flametail){1,N,1,N};
void ycl(){cin>>m;T.bt(1,1,6e4);}
int In(int l,int r,int x){return l<=x&&x<=r;}
void rol(int i){f(j,1,m)a[i][j-1]=a[i][j];a[i][m]=a[i][0];}
void su(int*a,int&n){sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;}
void cg(int x,int w,int&ans){if(v[x])--ans;v[x]+=w;if(v[x])++ans;}
void doing(){
cin>>n;
f(j,1,m)f(i,1,n)scanf("%d",&a[i][j]);
s=l=a[1][1];
f(i,1,n)f(j,1,m)s=max(s,a[i][j]),l=min(l,a[i][j]);
if(m==1)return printf("%d\n",s-l),void();/////////////////////////k=1//////////
f(i,1,n){
f(j,1,m)if(a[i][j]==s)p=1;
if(p){
f(j,1,m)swap(a[1][j],a[i][j]);
break;
}
}
f(j,1,m)if(a[1][j]==s)p=j;
f(_,2,p)rol(1);
register int L=0,R=s-l,C;
if(m==4){
all=0;
f(i,1,n)f(j,1,m)u[++all]=a[i][j];
su(u,all);
}
while(L<R){
C=(L+R)>>1;p=0;
if(L+200<R)C=L+(R-L)/4*3;
if(m==2){/////////////////////////////////////////////////////k=2//////////
p=1;q=0;
f(i,1,n){
f(_,1,m){
q|=(In(s-C,s,a[i][1])&&In(l,l+C,a[i][2]));
rol(i);
}
p&=q;q=0;
}
}else if(m==3){///////////////////////////////////////////////k=3//////////
f(lp,2,3){
q=tot=0;cnt=1;
f(i,1,n)f(_,1,m){
if(In(s-C,s,a[i][1])&&In(l,l+C,a[i][lp]))xw[b[++tot]=a[i][5-lp]].push_back(i);
rol(i);
}
su(b,tot);
f(i,1,tot){
for(int x:xw[b[i]])cg(x,1,q);
for(;b[cnt]+C<b[i];++cnt)for(int x:xw[b[cnt]])cg(x,-1,q);
if(q==n)p=1;
}
f(i,cnt,tot)for(int x:xw[b[i]])cg(x,-1,q);
f(i,1,n)f(j,1,m)xw[a[i][j]].clear();
}
}else{////////////////////////////////////////////////////////k=4//////////
f(lp,2,4)if(!p){
tot=0;
f(i,1,n)e[i].clear();
f(i,1,n)f(_,1,m){
if(In(s-C,s,a[i][1])&&In(l,l+C,a[i][lp])){
if(lp==2)xx=a[i][3],yy=a[i][4];
if(lp==3)xx=a[i][2],yy=a[i][4];
if(lp==4)xx=a[i][2],yy=a[i][3];
e[i].push_back((Flametail){xx,xx+C+1,yy,yy+C+1});
}
rol(i);
}
f(i,1,n){
ex=e[i].size();cnt=(1<<ex)-1;
f(S,1,cnt){
ls=____;zz=1;
f(w,0,ex-1)if((S>>w)&1)ls=ls*e[i][w],zz=-zz;
if(ls.a>=ls.b||ls.c>=ls.d)continue;
f[ls.c].push_back((Flametail){ls.a,ls.b,-zz,0});
f[ls.d].push_back((Flametail){ls.a,ls.b,zz,0});
}
}
f(i,1,all)c[i]=u[i],c[i+all]=u[i]+C+1;
inplace_merge(c+1,c+all+1,c+(tot=all*2)+1);o=0;
f(i,1,tot)if(f[q=c[i]].size()){
for(auto w:f[q])d[b[++o]=w.a]-=w.c,d[b[++o]=w.b]+=w.c;
f(i,1,o)if(d[r=b[i]])T.add(1,r,d[r]),d[r]=0;
if(T.a[1].c==n)p=1;f[q].clear();o=0;
}
}
}
if(p)R=C;
else L=C+1;
}
printf("%d\n",R);
}
signed main(){
int t;
cin>>t;
ycl();
while(t--)doing();
return 0;
}
```