题解：CF1423M Milutin's Plums

not_clever_syl · 2025-02-06 11:38:47 · 题解

这里直接给出 SMAWK 算法的主流程，它返回 n \times m 矩阵每一行的最小值位置。

首先把偶数行都挑出来，递归 \lfloor \frac n 2 \rfloor \times m 的子矩阵，得出偶数行的最小值位置，然后我们就可以轻松 O(n+m) 得到所有奇数行的最小值位置。

这样复杂度就是 O(n+m\log n)，虽然看着挺好了，但是我们无法接受。

这是因为当 m \gg n 时，有很多无用的冗余列，也就是不包含任何一行的最小值的列。

这时候我们引入一个 reduce 流程，它可以把 n \times m 的矩阵减小成 n \times \min(n,m) 的矩阵，且包含了所有行的最小值。 这样只需要每次 SMAWK 前 reduce 一下就可以保证复杂度为 O(n+m(1+\log \frac n m))，由于 m(1 + \log \frac n m) \leq m(1 + \frac n m)=m+n，所以还是线性。

reduce 需要额外维护一个指针 k，设 A_{i,j} 为传入的矩阵的第 i 行第 j 列位置上的值。

下面是算法流程。

赋值 k=1。
若行数大于等于列数（比较动态的行数和列数，因为后面会删列），则停止 reduce 过程。
比较 A_{k,k} 与 A_{k,k+1}，若 A_{k,k} > A_{k,k+1}，则删去第 k 列，令 k=\max(1,k-1)，回到第二步（注意此题内的 L(i) 是第一个最小值位置，所以等于是不需要删的，但是 CF 数据弱，两种写法都能过）。
否则此时 A_{k,k} \leq A_{k,k+1}，若 k=n 显然第 n+1 列无用，删去第 n+1 列，回到第二步。
否则此时 k<n，令 k=k+1，回到第二步。

算法不难理解，下面我们看这个算法为什么是对的。

以下使用 # 表示一行内的最小值位置，. 表示一行内的非最小值位置，! 是 A_{k,k} 所在位置的标记，a=b 表示标记 a 的位置是 b, b 是 . 或 #。

对于 !=# 的时刻 reduce 显然正确，考虑 !=. 的情况。

#....... !=.
.#...... $=.
.#......
.#.!....
...#....
.....#.$

我们考察 ! 与 # 同一列的时刻，此时怎么保证 reduce 不会把 ! 所在行删去呢？

考虑 ! 到 $ 的子矩阵，注意题目条件是每个子矩阵都有 L(i) \leq L(i+1)，因此 ! 一定是这个子矩阵中对应行的最小值位置，那么 A_{k,k}<A_{k,k+1}，所以 ! 的那一行一定可以被保留，可以保证 reduce 的正确性。

Code:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
int n,m;
map<int,int>mp[MAXN];
int ask(int x,int y){
    if(x>n||y>m||x<1||y<1)return 1e9+2;
    if(mp[x].count(y))return mp[x][y];
    cout<<"? "<<x<<' '<<y<<endl;
    int r;cin>>r;
    return mp[x][y]=r;
}
struct node{
    int pre,nxt;
}l[MAXN];
inline void lnk(int x,int y){l[x].nxt=y;l[y].pre=x;}
void reduce(vector<int>&xx,vector<int>&yy){
    if(xx.size()>=yy.size())return;
    int k=0,t=yy[0],tot=yy.size();
    lnk(0,yy[0]),lnk(yy.back(),0);
    for(int i=0;i+1<(int)yy.size();++i)lnk(yy[i],yy[i+1]);
    while((int)xx.size()<tot){
        int a=ask(xx[k],t),b=ask(xx[k],l[t].nxt);
        if(a>b){
            if(k){
                --k;
                lnk(l[t].pre,l[t].nxt);
                t=l[t].pre;
            }
            else{
                lnk(0,l[t].nxt);
                t=l[t].nxt;
            }
            --tot;
        }
        else{
            if(k<(int)xx.size()-1){
                ++k;
                t=l[t].nxt;
            }
            else{
                lnk(t,l[l[t].nxt].nxt);
                --tot;
            }
        }
    }
    while(l[t].pre)t=l[t].pre;
    yy.clear();
    for(;t;t=l[t].nxt)yy.emplace_back(t);
}
vector<int>SMAWK(vector<int>xx,vector<int>yy){
    reduce(xx,yy);
    if(xx.size()==1){
        return yy;
    }
    vector<int>tmp,r2;
    tmp.reserve(xx.size()/2);
    for(int i=1;i<(int)xx.size();i+=2)tmp.emplace_back(xx[i]);
    r2=SMAWK(tmp,yy);
    tmp.clear(),tmp.reserve(xx.size());
    int lst=yy[0],p=0;
    for(int i=0;i<(int)xx.size();++i){
        if(i&1){
            tmp.emplace_back(lst=r2[i>>1]);
        }
        else{
            if((i>>1)<(int)r2.size()&&lst==r2[i>>1]){
                tmp.emplace_back(lst);
            }
            else{
                int tt=((i>>1)==(int)r2.size()?yy.back():r2[i>>1]);
                while(p<(int)yy.size()&&yy[p]<lst)++p;
                int mn=ask(xx[i],lst),id=yy[p];
                while(p+1<(int)yy.size()&&yy[p+1]<=tt){
                    ++p;
                    int v=ask(xx[i],yy[p]);
                    if(v<mn){
                        mn=v;
                        id=yy[p];
                    }
                }
                tmp.emplace_back(id);
            }
        }
    }
    return tmp;
}
signed main(){
    cin>>n>>m;
    vector<int>xx,yy;
    xx.reserve(n),yy.reserve(m);
    for(int i=1;i<=n;++i)xx.emplace_back(i);
    for(int i=1;i<=m;++i)yy.emplace_back(i);
    auto res=SMAWK(xx,yy);
    int mn=1e9+5;
    for(int i=1;i<=n;++i){
        mn=min(mn,ask(i,res[i-1]));
    }
    cout<<"! "<<mn<<endl;
}