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

· · 题解

纪念在本题大力卡常翻盘。

首先转换题意，注意到一直进行一种操作一定不劣，则询问转换为对于矩阵内每行 mex 的最小值与每列 mex 最小值的最大值，下面只考虑每行 mex 最小值，另一种情况是相同的。

我们有两种做法：

第一种是对于每行，O(m^2) 地枚举所有区间，将答案记在区间右端点，那么一个矩阵的 mex 最小值就变成第 y_2 列上 [x_l,x_r] 中的最小值了，ST 表预处理即可，复杂度 O(nm^2\log n)。

第二种是把询问暴力拆到每行上，此时对于每一行有 O(q) 个询问，考虑扫描线从左到右，在权值线段树上第 i 个位置记录 i 最后一次出现的位置，因为 mex 是 O(m) 级别的所以线段树只用开到 m，然后扫到一个询问的右端点在线段树上二分最小的 i 使得 i 最后出现的位置小于询问左端点就是答案，复杂度 O(nq\log m)。

考虑平衡复杂度，设 N=nm 以及阈值 B，让 m \le B 时使用算法一，m > B 时使用算法二，复杂度即 O(B^2\frac{N}{B}\log{\frac{N}{B}}+q\frac{N}{B}\log B)。

取 B=\sqrt N，N,q 同阶，总复杂度即 O(N\sqrt N \log{\sqrt N})。

实测 B=800 很快，最慢点 1.6s 左右，常数小点能更快。

#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;
}