PKU2019 Cornfields

問題:

2019 -- Cornfields

問題概要:

N * N の整数(N<=250)で満たされたフィールドが与えられる。二次元区間は正方形でサイズは予めB*Bと決まっている。クエリの数Kが与えられるので、各クエリ毎に与えられる(R,C)の組が左上頂点(?)であるようなB*Bの正方形区間に含まれる最大の値と最小の値の差を出力しなさい。

解法:

セグメントツリーとか使ったり、何か嘘っぽいことしても通るらしいですが、1000msが恐かったのできちんとした解法っぽいのを使いました。

• 前処理:O(n^2)
• クエリ処理:O(1)

まあ蟻本にも載っているスライド最小値です。累積和の要領で横にやってから縦にやることで、二次元クエリを前処理しています。結構合理的だと思うこのデータ構造。4回くらいほとんど同じ処理が書いてある汚いソースになっています。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

typedef unsigned int uint;
int in() {
    int x = 0, c;
    for (; (uint)((c = getchar()) - '0') >= 10; ) { if (c == '-') return -in(); if (!~c) throw ~0; }
    do { x = (x << 3) + (x << 1) + (c - '0'); } while ((uint)((c = getchar()) - '0') < 10);
    return x;
}


int inp[250][250];
int query1[250][250];
int query2[250][250];
int deq[250];
int main(){
	int N = in() , B = in() , K = in();
	for(int i = 0 ; i < N ; i++){
		for(int j = 0 ; j < N ; j++){
			inp[i][j] = in();
		}
	}
	/*横にやる(最大)*/
	for(int i = 0 ; i < N ; i++){
		int s = 0 , t = 0;
		for(int j = 0 ; j < N ; j++){
			while(s < t && inp[i][deq[t-1]] <= inp[i][j] ) --t;
			deq[t++] = j;
			if(j-B+1 >= 0){
				query1[i][j-B+1] = inp[i][deq[s]];
				while(s < t && deq[s] <= j-B+1) ++s;
			}
		}
	}
	/*縦にやる(最大)*/
	for(int i = 0 ; i <= N ; i++){
		int s = 0 , t = 0;
		for(int j = 0 ; j <= N ; j++){
			while(s < t && query1[deq[t-1]][i] <= query1[j][i] ) --t;
			deq[t++] = j;
			if(j-B+1 >= 0){
				query1[j-B+1][i] = query1[deq[s]][i];
				while(s < t && deq[s] <= j-B+1) ++s;
			}
		}
	}
	/*横にやる(最小)*/
	for(int i = 0 ; i < N ; i++){
		int s = 0 , t = 0;
		for(int j = 0 ; j < N ; j++){
			while(s < t && inp[i][deq[t-1]] >= inp[i][j] ) --t;
			deq[t++] = j;
			if(j-B+1 >= 0){
				query2[i][j-B+1] = inp[i][deq[s]];
				while(s < t && deq[s] <= j-B+1) ++s;
			}
		}
	}
	/*縦にやる(最小)*/
	for(int i = 0 ; i <= N ; i++){
		int s = 0 , t = 0;
		for(int j = 0 ; j <= N ; j++){
			while(s < t && query2[deq[t-1]][i] >= query2[j][i] ) --t;
			deq[t++] = j;
			if(j-B+1 >= 0){
				query2[j-B+1][i] = query2[deq[s]][i];
				while(s < t && deq[s] <= j-B+1) ++s;
			}
		}
	}
	
	for(int i = 0 ; i < K ; i++){
		int a = in() - 1 , b = in() - 1;
		printf("%d\n",query1[a][b] - query2[a][b]);
	}
}