二维 ST 表

ST表 序列dp 倍增 序列最大值查询

题目描述

给定 $n\times n$ 的矩阵 $a$ 和 $q$ 个询问，每一个询问都是 $(x_1,y_1,x_2,y_2)$ 的形式，求 $\underset{i=x_1}{\overset{x_2}{\max }}\underset{j=y_1}{\overset{y_2}{\max }}{a}_{i,j}$。

提示说明

• $1\le n\le 1000$；
• $1\le a_{i,j}\le n^2$，$a$ 当中所有元素都是唯一的；
• $1\le q\le 10^6$。

对于 $40\%$ 的数据，$q$ 只有 $10^5$，数据极小，随便搞。