CF1195E OpenStreetMap

题目传送门

思路

单调队列板子。

设 \(b_{i,j}\) 表示第 \(i\) 行，区间为 \(j\) 到 \(j+y-1\) 的最小值，不难发现这个可以用单调队列 \(O(nm)\) 预处理出来。

接下来我们的问题就转化成了有一个矩阵，求所有宽为 \(1\)，长为 \(x\) 的子矩阵的最小值之和。

这个问题也十分好做，直接枚举列，然后在每一行单调队列即可。

代码

/*
A tree without skin will surely die. 
A man without face is invincible.
*/
#include<bits/stdc++.h>
using namespace std;
int const N=3e3+10;
int ans,n,m,a[N][N],b[N][N],g[N*N];
struct node{int w,id;}q[N];
inline void go(int x,int y){
	for (int i=1;i<=n;++i){
		int l=1,r=0;
		for (int j=1;j<=y;++j){
			while (l<=r && q[r].w>=a[i][j]) --r;
			q[++r].w=a[i][j];q[r].id=j;
		}
		b[i][1]=q[l].w;
		for (int j=y+1;j<=m;++j){
			while (q[l].id<=j-y && l<=r) ++l;
 			while (l<=r && q[r].w>=a[i][j]) --r;
 			q[++r].w=a[i][j];q[r].id=j;
 			b[i][j-y+1]=q[l].w;
		}
	}
	for (int j=1;j<=m-y+1;++j){
		int l=1,r=0;
		for (int i=1;i<=x;++i){
			while (l<=r && q[r].w>=b[i][j]) --r;
			q[++r].w=b[i][j];q[r].id=i;
		}
		ans+=q[l].w;
		for (int i=x+1;i<=n;++i){
			while (q[l].id<=i-x && l<=r) ++l;
			while (l<=r && q[r].w>=b[i][j]) --r;
			q[++r].w=b[i][j];q[r].id=i;ans+=q[l].w;
		}
	}
}
signed main(){
	//读入
	for (int i=1;i<=n*m;++i) g[i]=(g[i-1]*xx%zz+yy)%zz;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) a[i][j]=g[(i-1)*m+j-1];
	go(x,y);//输出
	return 0;
}

原文地址：http://www.cnblogs.com/tx-lcy/p/16791321.html