2D RMQ 템플릿

다른 사람의 코드를 수정하고 클릭하여 링크를 열면 더욱 통용되는 템플릿이 됩니다. 다음은 템플릿의 사용 설명과 방법입니다.

#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include<algorithm>

#define N 500

using namespace std;

int pmax[N][N][11], pmin[N][N][10], a[N][N], n,m, q, width,high,maxans, minans;
//n*m   ，   （a,b）     ，     width，   high    rmq

void init_rmq()//n*m       
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			pmax[i][j][0] = pmin[i][j][0] = a[i][j];

	for (int i = 1; i <= n; i++)
		for (int k = 1; (1 << k) <= m; k++)
			for (int j = 1; j + (1 << k) - 1 <= m; j++)
			{
				pmax[i][j][k] = max(pmax[i][j][k - 1], pmax[i][j + (1 << (k - 1))][k - 1]);
				pmin[i][j][k] = min(pmin[i][j][k - 1], pmin[i][j + (1 << (k - 1))][k - 1]);
			}
}

void read()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	init_rmq();
}

void askrmq(int a, int b)//   （a,b）     ，     width，   high    rmq
{
	int k = (int)(log(double(width)) / log(2.0));
	maxans = 0; minans = int(1e9);
	int l = b, r = b + width - 1;
	for (int i = a; i<a + high; i++)
	{
		maxans = max(maxans, max(pmax[i][l][k], pmax[i][r - (1 << k) + 1][k]));
		minans = min(minans, min(pmin[i][l][k], pmin[i][r - (1 << k) + 1][k]));
	}
}

void go()
{
	for (int i = 1, a, b; i <= q; i++)//q   
	{
		scanf("%d%d", &a, &b);
		askrmq(a, b);
		printf("%d
", maxans - minans);
	}
}

int main()
{
#ifdef CDZSC
	freopen("i.txt", "r", stdin);
#endif // CDZSC

	while (scanf("%d%d%d%d%d", &n,&m, &width,&high,&q) != EOF)
	{
		read();
		go();
	}
	return 0;
}

템플릿입니다.

#define N 500

using namespace std;

int pmax[N][N][11], pmin[N][N][10], a[N][N], n,m, q, width,high,maxans, minans;
//n*m   ，   （a,b）     ，     width，   high    rmq

void init_rmq()//n*m       
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			pmax[i][j][0] = pmin[i][j][0] = a[i][j];

	for (int i = 1; i <= n; i++)
		for (int k = 1; (1 << k) <= m; k++)
			for (int j = 1; j + (1 << k) - 1 <= m; j++)
			{
				pmax[i][j][k] = max(pmax[i][j][k - 1], pmax[i][j + (1 << (k - 1))][k - 1]);
				pmin[i][j][k] = min(pmin[i][j][k - 1], pmin[i][j + (1 << (k - 1))][k - 1]);
			}
}

void read()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &a[i][j]);
	init_rmq();
}

void askrmq(int a, int b)//   （a,b）     ，     width，   high    rmq
{
	int k = (int)(log(double(width)) / log(2.0));
	maxans = 0; minans = int(1e9);
	int l = b, r = b + width - 1;
	for (int i = a; i<a + high; i++)
	{
		maxans = max(maxans, max(pmax[i][l][k], pmax[i][r - (1 << k) + 1][k]));
		minans = min(minans, min(pmin[i][l][k], pmin[i][r - (1 << k) + 1][k]));
	}
}