RMQ模板

/*
 * Author: rush
 * Created Time:  2010年07月28日 星期三 09时29分05秒
 * File Name: icpc/hdu3486.cpp
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;

const int maxn = 200000 + 5;
int n, k, a[maxn];
int rmax[20][maxn];
void make()
{
	for (int j = 0; j < n; ++j)
		rmax[0][j] = a[j];
	for (int i = 0; i + 1 < 20; ++i)
		for (int j = 0; j + (1 << i) < n; ++j)
			rmax[i + 1][j] = max(rmax[i][j], rmax[i][j + (1 << i)]);
}
// [begin, end)
int query(int begin, int end)
{
	int k = 0;
	while ((1 << (k + 1)) < end - begin) ++k;
	return max(rmax[k][begin], rmax[k][end - (1 << k)]);
}

int main()
{
	while (scanf("%d%d", &n, &k) != EOF)
	{
		if (n < 0 && k < 0) break;
		for (int i = 0; i < n; ++i)
			scanf("%d", &a[i]);
		make();
		int m, L, prev = -1, sum, i, j;
		for (m = 1; m <= n; ++m)
		{
			L = n / m;
			if (L != prev) 
				sum = 0, i = 0, j = 0;
			while (i + L <= n && j < m)
			{
				sum += query(i, i + L);
				i += L;
				++j;
			}
			prev = L;
			if (sum > k) break;
		}
		printf("%d\n", m <= n ? m : -1);
	}
    return 0;
}

update 20101230:
二维RMQ

/*
 * Author: rush
 * Created Time:  2010年12月30日 星期四 15时59分14秒
 * File Name: icpc/pku2019_2.cpp
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define two(x) (1 << x)
#define min4(a, b, c, d) min(min(min(a, b), c), d)
#define max4(a, b, c, d) max(max(max(a, b), c), d)
using namespace std;
typedef long long LL;

int N, B, K;
int mat[255][255];

int rmin[10][255][255], rmax[10][255][255];
void make() {
	FOR(i, N) FOR(j, N) rmin[0][i][j] = rmax[0][i][j] = mat[i][j];
	for (int k = 0; k + 1 < 10; ++k)
		for (int i = 0; i + two(k) < N; ++i)
			for (int j = 0; j + two(k) < N; ++j) {
				rmin[k + 1][i][j] = min4(rmin[k][i][j], rmin[k][i][j + two(k)], rmin[k][i + two(k)][j], rmin[k][i + two(k)][j + two(k)]);
				rmax[k + 1][i][j] = max4(rmax[k][i][j], rmax[k][i][j + two(k)], rmax[k][i + two(k)][j], rmax[k][i + two(k)][j + two(k)]);
			}
}
int query(int x, int y) {
	int k = 0;
	while (two(k + 1) <= B) ++k;
	int tmin = min4(rmin[k][x][y], rmin[k][x][y + B - two(k)], rmin[k][x + B - two(k)][y], rmin[k][x + B - two(k)][y + B - two(k)]);
	int tmax = max4(rmax[k][x][y], rmax[k][x][y + B - two(k)], rmax[k][x + B - two(k)][y], rmax[k][x + B - two(k)][y + B - two(k)]);
	return tmax - tmin;
}
int main()
{
	scanf("%d%d%d", &N, &B, &K);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			scanf("%d", &mat[i][j]);
	make();
	while (K--) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x, --y;
		printf("%d\n", query(x, y));
	}
    return 0;
}