题解：CF1423M Milutin's Plums

这里直接给出 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 显然正确，考虑 !=. 的情况。

TEXT

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

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

考虑 ! 到 $ 的子矩阵，注意题目条件是每个子矩阵都有

L(i) \leq L(i+1)

，因此 ! 一定是这个子矩阵中对应行的最小值位置，那么

A_{k,k}<A_{k,k+1}

，所以 ! 的那一行一定可以被保留，可以保证 reduce 的正确性。

Code:

CPP

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

题解：CF1423M Milutin's Plums

文章操作

相关推荐

评论

题解：CF1423M Milutin's Plums