洛谷 [P2216] 理想的正方形

二维单调队列

先横向跑一边单调队列，记录下每一行长度为n的区间的最值

在纵向跑一边单调队列，得出结果

注意，mi要初始化为一个足够大的数

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

int init() {

	int rv = 0, fh = 1;

	char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') fh = -1;

		c = getchar();

	}

	while(c >= '0' && c <='9') {

		rv = (rv<<1) + (rv<<3) + c - '0';

		c = getchar();

	}

	return fh * rv;

}

const int MAXN = 2005;

int num[MAXN][MAXN], ma[MAXN][MAXN], mi[MAXN][MAXN], n, a, b, ans = 0x7fffffff;

struct ddque{

	int que[MAXN<<3], head, tail;

	void clear(bool opt){

		que[0] = opt? 0: 0x7fffffff; //注意这里

		head = tail = 0;

	}

	void insert(int x, bool opt){

		if(!opt) {

			while(que[tail] > x && tail >= head) tail--;

			que[++tail] = x;

		}else {

			while(que[tail] < x && tail >= head) tail--;

			que[++tail] = x;

		}

	}

	void pop(int x){

		if(que[head] == x) head++;

	}

	int query(){

		return que[head];

	}

}q1, q2;

int main() {

	freopen("in.txt", "r", stdin);

	memset(mi,0x7f,sizeof(mi));

	a = init(); b = init(); n = init();

	for(int i = 1 ; i <= a ; i++) {

		for(int j = 1 ; j <=b ; j++) {

			num[i][j] = init();

		}

	}

	for(int i = 1 ; i <= a ; i++) {

		q1.clear(0); q2.clear(1);

		for(int j = 1 ; j <= n ; j++) {

			q1.insert(num[i][j], 0);

			q2.insert(num[i][j], 1);

		}

		ma[i][n] = q2.query();

		mi[i][n] = q1.query();

		for(int j = n + 1 ; j <= b ; j++) {

			q1.insert(num[i][j], 0);

			q2.insert(num[i][j], 1);

			q1.pop(num[i][j - n]);

			q2.pop(num[i][j - n]);

			ma[i][j] = q2.query();

			mi[i][j] = q1.query();

		}

	}

	for(int j = n ; j <= b ; j++) {

		q1.clear(0); q2.clear(1);

		for(int i = 1 ; i <= n ; i++) {

			q1.insert(mi[i][j], 0);

			q2.insert(ma[i][j], 1);

		}

		ans = min(ans, q2.query() - q1.query());

		for(int i = n + 1 ; i <= a ; i++) {

			q1.insert(mi[i][j], 0);

			q2.insert(ma[i][j], 1);

			q1.pop(mi[i - n][j]);

			q2.pop(ma[i - n][j]);

			ans = min(ans, q2.query() - q1.query());

		}

	}

	cout<<ans<<endl;

	fclose(stdin);

	return 0;

}

巴特西

洛谷 [P2216] 理想的正方形

二维单调队列

最新文章

热门文章