rt

没有过样例 lock.5 中部分数据点

思路是容斥加二维数点，实在调不出来了，有没有人能帮忙看看哪里错了

#include<bits/stdc++.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
namespace IO{
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];++i)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
const int maxk = 5,maxn = 5e4+114,maxv=3e4+10;
int a[maxk][maxn],k;
int ans(int j,int n){
	int mx=0,mi=65535;
	for(int i=1;i<=n;++i) mx=max(mx,a[j][i]),mi=min(mi,a[j][i]);
	return mx-mi;
}
vector<int> ch[maxn];//剩下一行可能的选择
int sum[maxv];//差分数组
int n;
int lwx;
inline void add(int l,int r,int val){//差分数组上修改
	r=min(r,maxv-5);
	sum[l]+=val;
	sum[r+1]-=val;
	lwx=max(lwx,r+1);
}
inline void maintain(){//统计差分数组
	for(int i=1;i<=lwx;++i) sum[i]+=sum[i-1];
}
bool check(int pos,int mx,int mi,int val){//最大值放在第 1 行，最小值放在第 pos 行 k=3 极值为 val 是否合法
	for(int i=0;i<=lwx;++i) sum[i]=0;
	lwx=0;
	for(int i=1;i<=n;++i) ch[i].clear();
	int r1=mx,l1=r1-val;
	int l2=mi,r2=l2+val;
	int last;
	for(int i=1;i<=n;++i){
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			ch[i].push_back(a[((pos-2)^1)+2][i]);
		}
		last=a[1][i];
		a[1][i]=a[2][i];
		a[2][i]=a[3][i];
		a[3][i]=last;
		//转锁调整数组
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			ch[i].push_back(a[((pos-2)^1)+2][i]);
		}
		last=a[1][i];
		a[1][i]=a[2][i];
		a[2][i]=a[3][i];
		a[3][i]=last;
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			ch[i].push_back(a[((pos-2)^1)+2][i]);
		}
		if(ch[i].size()==0) return false;
		if(ch[i].size()==1){
			add(ch[i][0],ch[i][0]+val,1);
		}
		else if(ch[i].size()==2){
			add(ch[i][0],ch[i][0]+val,1);
			add(ch[i][1],ch[i][1]+val,1);
			int l=max(ch[i][0],ch[i][1]),r=min(ch[i][0]+val,ch[i][1]+val);
			if(l<=r)
				add(l,r,-1);
			//容斥处理
		}
		else {
			int l=min(ch[i][0],min(ch[i][1],ch[i][2])),r=mx;
			add(l,r,1);
		}
	}
	maintain();
	for(int i=1;i<=n;++i){
		if(ch[i].size()==0) continue;
		for(int u:ch[i])
			if(sum[u]==n)//被所有区间包含，也就是区间 [u-val,u] 包含所有点
				return true;
	}	
	return false;
}
int tree[maxv];
vector< pair<int,int> > opt[maxn]; //pos:val
vector<int> query[maxn];
inline void Add(int x,int val){
	x++;
	while(x<maxv){
		tree[x]+=val;
		x+=(x&(-x));
	}
}
inline int Pre(int x){
	x++;
	int res=0;
	while(x>0){
		res+=tree[x];
		x-=(x&(-x));
	}
	return res;
}
inline void add_p(pair<int,int> A,pair<int,int> B,int val){
	A.first=min(A.first,maxv-5);
	A.second=min(A.second,maxv-5);
	B.first=min(B.first,maxv-5);
	B.second=min(B.second,maxv-5);
	opt[B.first].push_back(make_pair(B.second,val));
	opt[A.first-1].push_back(make_pair(B.second,-val));
	opt[B.first].push_back(make_pair(A.second-1,-val));
	opt[A.first-1].push_back(make_pair(A.second-1,val));
	//二维差分 
}
//值域平移 1 
vector< pair<int,int> > chifan[maxn];
bool Check(int pos,int mx,int mi,int val){//最大值放在第 1 行，最小值放在第 pos 行 k=4 极值为 val 是否合法
	for(int i=0;i<maxv;i++) tree[i]=0,opt[i].clear(),query[i].clear();
	for(int i=1;i<=n;i++) chifan[i].clear();
	int r1=mx,l1=r1-val;
	int l2=mi,r2=l2+val;
	int last;
	for(int i=1;i<=n;i++){
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			if(pos==2){
				chifan[i].push_back(make_pair(a[3][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
			}
			else if(pos==3){
				chifan[i].push_back(make_pair(a[2][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else{
				chifan[i].push_back(make_pair(a[2][i],a[3][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
		}
		last=a[1][i];
		a[1][i]=a[2][i];
		a[2][i]=a[3][i];
		a[3][i]=a[4][i];
		a[4][i]=last;
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			if(pos==2){
				chifan[i].push_back(make_pair(a[3][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else if(pos==3){
				chifan[i].push_back(make_pair(a[2][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else{
				chifan[i].push_back(make_pair(a[2][i],a[3][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
		}
		last=a[1][i];
		a[1][i]=a[2][i];
		a[2][i]=a[3][i];
		a[3][i]=a[4][i];
		a[4][i]=last;
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			if(pos==2){
				chifan[i].push_back(make_pair(a[3][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else if(pos==3){
				chifan[i].push_back(make_pair(a[2][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else{
				chifan[i].push_back(make_pair(a[2][i],a[3][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
		}
		last=a[1][i];
		a[1][i]=a[2][i];
		a[2][i]=a[3][i];
		a[3][i]=a[4][i];
		a[4][i]=last;
		if(l1<=a[1][i]&&a[1][i]<=r1&&l2<=a[pos][i]&&a[pos][i]<=r2){//确定区间的行填的数合法合法
			if(pos==2){
				chifan[i].push_back(make_pair(a[3][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else if(pos==3){
				chifan[i].push_back(make_pair(a[2][i],a[4][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
			else{
				chifan[i].push_back(make_pair(a[2][i],a[3][i]));
				query[chifan[i].back().first].push_back(chifan[i].back().second);
				
			}
		}
		//下面开始容斥处理贡献 
		if(chifan[i].size()==0) return false;
		if(chifan[i].size()==1){
			add_p(chifan[i][0],make_pair(chifan[i][0].first+val,chifan[i][0].second+val),1);
		}
		else if(chifan[i].size()==2){
			add_p(chifan[i][0],make_pair(chifan[i][0].first+val,chifan[i][0].second+val),1);
			add_p(chifan[i][1],make_pair(chifan[i][1].first+val,chifan[i][1].second+val),1);
			pair<int,int> l=make_pair(max(chifan[i][0].first,chifan[i][1].first),max(chifan[i][0].second,chifan[i][1].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][1].first+val),min(chifan[i][0].second+val,chifan[i][1].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);			
			//容斥处理
		}
		else if(chifan[i].size()==3){
			add_p(chifan[i][0],make_pair(chifan[i][0].first+val,chifan[i][0].second+val),1);
			add_p(chifan[i][1],make_pair(chifan[i][1].first+val,chifan[i][1].second+val),1);
			add_p(chifan[i][2],make_pair(chifan[i][2].first+val,chifan[i][2].second+val),1);
			pair<int,int> l=make_pair(max(chifan[i][0].first,chifan[i][1].first),max(chifan[i][0].second,chifan[i][1].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][1].first+val),min(chifan[i][0].second+val,chifan[i][1].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][0].first,chifan[i][2].first),max(chifan[i][0].second,chifan[i][2].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][2].first+val),min(chifan[i][0].second+val,chifan[i][2].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][1].first,chifan[i][2].first),max(chifan[i][1].second,chifan[i][2].second)),r=make_pair(min(chifan[i][1].first+val,chifan[i][2].first+val),min(chifan[i][1].second+val,chifan[i][2].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][0].first,max(chifan[i][1].first,chifan[i][2].first)),max(chifan[i][0].second,max(chifan[i][1].second,chifan[i][2].second))),r=make_pair(min(chifan[i][0].first+val,min(chifan[i][1].first+val,chifan[i][2].first+val)),min(chifan[i][0].second+val,min(chifan[i][1].second+val,chifan[i][2].second+val)));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,1);
		}
		else{
			add_p(chifan[i][0],make_pair(chifan[i][0].first+val,chifan[i][0].second+val),1);
			add_p(chifan[i][1],make_pair(chifan[i][1].first+val,chifan[i][1].second+val),1);
			add_p(chifan[i][2],make_pair(chifan[i][2].first+val,chifan[i][2].second+val),1);
			add_p(chifan[i][3],make_pair(chifan[i][3].first+val,chifan[i][3].second+val),1);
			pair<int,int> l=make_pair(max(chifan[i][0].first,chifan[i][1].first),max(chifan[i][0].second,chifan[i][1].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][1].first+val),min(chifan[i][0].second+val,chifan[i][1].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][0].first,chifan[i][2].first),max(chifan[i][0].second,chifan[i][2].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][2].first+val),min(chifan[i][0].second+val,chifan[i][2].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][1].first,chifan[i][2].first),max(chifan[i][1].second,chifan[i][2].second)),r=make_pair(min(chifan[i][1].first+val,chifan[i][2].first+val),min(chifan[i][1].second+val,chifan[i][2].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][0].first,chifan[i][3].first),max(chifan[i][0].second,chifan[i][3].second)),r=make_pair(min(chifan[i][0].first+val,chifan[i][3].first+val),min(chifan[i][0].second+val,chifan[i][3].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][1].first,chifan[i][3].first),max(chifan[i][1].second,chifan[i][3].second)),r=make_pair(min(chifan[i][1].first+val,chifan[i][3].first+val),min(chifan[i][1].second+val,chifan[i][3].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][2].first,chifan[i][3].first),max(chifan[i][2].second,chifan[i][3].second)),r=make_pair(min(chifan[i][2].first+val,chifan[i][3].first+val),min(chifan[i][2].second+val,chifan[i][3].second+val));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
			l=make_pair(max(chifan[i][0].first,max(chifan[i][1].first,chifan[i][2].first)),max(chifan[i][0].second,max(chifan[i][1].second,chifan[i][2].second))),r=make_pair(min(chifan[i][0].first+val,min(chifan[i][1].first+val,chifan[i][2].first+val)),min(chifan[i][0].second+val,min(chifan[i][1].second+val,chifan[i][2].second+val)));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,1);
			l=make_pair(max(chifan[i][1].first,max(chifan[i][2].first,chifan[i][3].first)),max(chifan[i][1].second,max(chifan[i][2].second,chifan[i][3].second))),r=make_pair(min(chifan[i][1].first+val,min(chifan[i][2].first+val,chifan[i][3].first+val)),min(chifan[i][1].second+val,min(chifan[i][2].second+val,chifan[i][3].second+val)));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,1);
			l=make_pair(max(chifan[i][0].first,max(chifan[i][2].first,chifan[i][3].first)),max(chifan[i][0].second,max(chifan[i][2].second,chifan[i][3].second))),r=make_pair(min(chifan[i][0].first+val,min(chifan[i][2].first+val,chifan[i][3].first+val)),min(chifan[i][0].second+val,min(chifan[i][2].second+val,chifan[i][3].second+val)));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,1);
			l=make_pair(max(chifan[i][0].first,max(chifan[i][1].first,chifan[i][3].first)),max(chifan[i][0].second,max(chifan[i][1].second,chifan[i][3].second))),r=make_pair(min(chifan[i][0].first+val,min(chifan[i][1].first+val,chifan[i][3].first+val)),min(chifan[i][0].second+val,min(chifan[i][1].second+val,chifan[i][3].second+val)));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,1);
			l=make_pair(max(chifan[i][0].first,max(chifan[i][1].first,max(chifan[i][2].first,chifan[i][3].first))),max(chifan[i][0].second,max(chifan[i][1].second,max(chifan[i][2].second,chifan[i][3].second)))),r=make_pair(min(chifan[i][0].first+val,min(chifan[i][1].first+val,min(chifan[i][2].first+val,chifan[i][3].first+val))),min(chifan[i][0].second+val,min(chifan[i][1].second+val,min(chifan[i][2].second+val,chifan[i][3].second+val))));
			if(l.first<=r.first&&l.second<=r.second)
				add_p(l,r,-1);
		}
	}
	for(int i=maxv-1;i>=0;i--){
		for(pair<int,int> u:opt[i]){
			Add(u.first,u.second);
		}
		for(int u:query[i]){
			if(Pre(maxv-3)-Pre(u-1)>=n){
				return true;
			}
		}
	}
	return false;
}
void work(){
	read(n);
	for(int i=1;i<=k;++i){
		for(int j=1;j<=n;++j){
			read(a[i][j]);
		}
	}
	if(k==1){
		write(ans(1,n));
		putchar('\n');
	}
	else if(k==2){
		for(int i=1;i<=n;++i){
			if(a[1][i]<a[2][i]) swap(a[1][i],a[2][i]);
		}
		write(max(ans(1,n),ans(2,n)));
		putchar('\n');
	}
	else if(k==3){
		int mx=0,mi=65535;
		for(int i=1;i<=k;++i)
			for(int j=1;j<=n;++j){
				mx=max(mx,a[i][j]);
				mi=min(mi,a[i][j]);
			}
		int l=-1,r=(mx-mi);
		while(l+1<r){
			int mid=(l+r)>>1;
			if(check(2,mx,mi,mid)==true||check(3,mx,mi,mid)==true){
				r=mid;
			}
			else{
				l=mid;
			}
		}
		write(r);
		putchar('\n');
	}
	else{
		int mx=0,mi=65535;
		for(int i=1;i<=k;++i)
			for(int j=1;j<=n;++j){
				mx=max(mx,a[i][j]);
				mi=min(mi,a[i][j]);
			}
		int l=-1,r=(mx-mi);
		while(l+1<r){
			int mid=(l+r)>>1;
			if(Check(2,mx,mi,mid)==true||Check(3,mx,mi,mid)==true||Check(4,mx,mi,mid)==true){
				r=mid;
			}
			else{
				l=mid;
			}
		}
		write(r);
		putchar('\n');
	}
	return ;
}
signed main(){
	//freopen("lock5.in","r",stdin);
	//freopen("lock5.out","w",stdout);
	int t;
	read(t);
	read(k);
	while(t--) work();
}