专栏文章

题解：P13664 「TPOI-5C」mαtrixing ωiθ μ

WWatersphereWater
P13664题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miog53wj
此快照首次捕获于
2025/12/02 18:39
3 个月前
此快照最后确认于
2025/12/02 18:39
3 个月前
查看原文
纪念在本题大力卡常翻盘。
首先转换题意，注意到一直进行一种操作一定不劣，则询问转换为对于矩阵内每行 mex 的最小值与每列 mex 最小值的最大值，下面只考虑每行 mex 最小值，另一种情况是相同的。
我们有两种做法：
第一种是对于每行，O(m2)O(m^2) 地枚举所有区间，将答案记在区间右端点，那么一个矩阵的 mex 最小值就变成第 y2y_2 列上 [xl,xr][x_l,x_r] 中的最小值了，ST 表预处理即可，复杂度 O(nm2log⁡n)O(nm^2\log n)。
第二种是把询问暴力拆到每行上，此时对于每一行有 O(q)O(q) 个询问，考虑扫描线从左到右，在权值线段树上第 ii 个位置记录 ii 最后一次出现的位置，因为 mex 是 O(m)O(m) 级别的所以线段树只用开到 mm，然后扫到一个询问的右端点在线段树上二分最小的 ii 使得 ii 最后出现的位置小于询问左端点就是答案，复杂度 O(nqlog⁡m)O(nq\log m)。
考虑平衡复杂度，设 N=nmN=nm 以及阈值 BB，让 m≤Bm \le B 时使用算法一，m>Bm > B 时使用算法二，复杂度即 O(B2NBlog⁡NB+qNBlog⁡B)O(B^2\frac{N}{B}\log{\frac{N}{B}}+q\frac{N}{B}\log B)。
取 B=NB=\sqrt N，N,qN,q 同阶，总复杂度即 O(NNlog⁡N)O(N\sqrt N \log{\sqrt N})。
实测 B=800B=800 很快，最慢点 1.6s 左右，常数小点能更快。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=3e5,B=800;
int n,m,q,vis[N+5],xl[N+5],xr[N+5],yl[N+5],yr[N+5],ans1[N+5],ans2[N+5];
vector<int> ma[N+5],tmp[N+5],ret[N+5];
inline void flip(){
	for(int i=1;i<=n;i++){
	    tmp[i].resize(m+5);
		for(int j=1;j<=m;j++) tmp[i][j]=ma[i][j];
	}
	swap(n,m);
	for(int i=1;i<=n;i++){
		ma[i].resize(m+5);
		for(int j=1;j<=m;j++) ma[i][j]=tmp[j][i];
	}
	for(int i=1;i<=q;i++){
		swap(xl[i],yl[i]);
		swap(xr[i],yr[i]);
	}
	return;
}
vector<int> rec2[N+5];
struct SGT{
	int mn[5*N+5];
	inline void build(int pos,int lp,int rp){
		mn[pos]=0;
		if(lp==rp) return;
		int mid=(lp+rp)/2;
		build(pos*2,lp,mid),build(pos*2+1,mid+1,rp);
		return;
	}
	inline void pushup(int pos){mn[pos]=min(mn[pos*2],mn[pos*2+1]); return;}
	inline void update(int pos,int to,int lp,int rp,int val){
		if(rp<to||to<lp) return;
		if(lp==rp&&lp==to){mn[pos]=val; return;}
		int mid=(lp+rp)/2;
		update(pos*2,to,lp,mid,val),update(pos*2+1,to,mid+1,rp,val);
		pushup(pos); return;
	}
	inline int query(int pos,int lp,int rp,int lim){
		if(lp==rp) return lp;
		int mid=(lp+rp)/2;
		if(mn[pos*2]<lim) return query(pos*2,lp,mid,lim);
		else return query(pos*2+1,mid+1,rp,lim);
	}
}sgt;
inline void work1(){
	for(int i=1;i<=q;i++) ans1[i]=m;
	for(int o=1;o<=n;o++){
		for(int i=1;i<=q;i++) if(xl[i]<=o&&o<=xr[i]) rec2[yr[i]].push_back(i);
		sgt.build(1,0,m);
		for(int i=1;i<=m;i++){
			if(ma[o][i]<=m) sgt.update(1,ma[o][i],0,m,i);
			for(int j:rec2[i]) ans1[j]=min(ans1[j],sgt.query(1,0,m,yl[j]));
			rec2[i].clear();
		}
	}
	for(int i=1;i<=q;i++) ans2[i]=max(ans2[i],ans1[i]);
	return;
}
struct ST{
	int mn[20][N+5],lg[N+5];
	inline void build(int cod){
		for(int i=2;i<=n;i++) lg[i]=lg[i/2]+1;
		for(int i=1;i<=n;i++) mn[0][i]=ret[i][cod];
		for(int i=1;i<=lg[n];i++){
			for(int j=1;j<=n-(1<<i)+1;j++) mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<(i-1))]);
		}
		return;
	}
	inline int query(int l,int r){
		int len=lg[r-l+1];
		return min(mn[len][l],mn[len][r-(1<<len)+1]);
	}
}st;
vector<int> rec[B+5][B+5];
inline void work2(){
	for(int i=1;i<=q;i++) rec[yl[i]][yr[i]].push_back(i),ans1[i]=0;
	for(int i=1;i<=n;i++) ret[i].resize(m+5);
	for(int l=1;l<=m;l++){
		for(int i=1;i<=n;i++){
			int mx=0;
			for(int r=l;r<=m;r++){
				if(ma[i][r]<=m) vis[ma[i][r]]=1;
				while(vis[mx]) mx++;
				ret[i][r]=mx;
			}
			for(int j=0;j<=m;j++) vis[j]=0;
		}
		for(int r=l;r<=m;r++){
			st.build(r);
			for(int i:rec[l][r]) ans1[i]=st.query(xl[i],xr[i]);
			rec[l][r].clear();
		}
	}
	for(int i=1;i<=q;i++) ans2[i]=max(ans2[i],ans1[i]);
	return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		ma[i].resize(m+5);
		for(int j=1;j<=m;j++) cin>>ma[i][j];
	}
	int jud=1;
	for(int i=1;i<=q;i++) cin>>xl[i]>>yl[i]>>xr[i]>>yr[i],jud&=(xl[i]==1&&yl[i]==1);
	if(m<=B) work2();
	else work1();
	flip();
	if(m<=B) work2();
	else work1();
	for(int i=1;i<=q;i++) cout<<ans2[i]<<"\n";
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...