Description
为了准备校庆庆典，学校招募了一些学生组成了一个方阵，准备在庆典上演出。
这个方阵是一个nm的矩形，第i行第j列有一名学生，他有一个能力值Ai,j。
校长会定期检查一个pq的方阵，询问这个方阵的学生能力值之和，或是学生能力值的最大值，或是学生能力值的最小值。由于校长不喜欢一个方阵长宽之比差太多，他每次询问的方阵的长不会超过宽的两倍。作为校庆筹办组组长的你，应该迅速并准确的回答校长所问的问题。
Input
第一行包含两个整数n,m，表示这个方阵的两条边的长度。
接下来n行，每行m个数，表示每个学生的能力值。
接下来一行包含一个整数q，表示校长的询问数。
接下来q行，每行先一个字符串s，接下来4个整数x1，y1，x2，y2，保证x1≤x2，y1≤y2，设以第x1行y1列为左上角，第x2行y2列为右下角的方阵为P。(本题为0下标)
若字符串内容为“SUM”，请求出P中所有学生的能力值之和。
若字符串内容为“MAX”，请求出P中所有学生的能力值的最大值。
若字符串内容为“MIN”，请求出P中所有学生的能力值的最小值。
Output
输出总共q行，第i行的数为第i组询问对应的答案ansi。
Sample Input
3 3
1 2 3
4 5 6
7 8 9
3
SUM 0 0 1 1
MAX 0 0 2 2
MIN 0 1 1 1
Sample Output
12
9
2
Hint
【样例解释】
对于第一组询问，能力值之和为1+2+4+5=12。
对于第二组询问，能力值最大的位置为第2行第2列。
对于第三组询问，能力值最小的位置为第0行第1列。
【数据规模和约定】
对于40%的数据，n,m≤200,q≤200
对于60%的数据，n,m≤300,q≤100000
对于80%的数据，n,m≤500,q≤500000
对于100%的数据，n,m≤800,q≤500000,0≤Aij≤3000,每个询问的方阵的长不超过宽的两倍。
思路
- 二维线段树或二维RMQ模板
- 代码为二维线段树
代码
#include <iostream>
#include <cstdio>
using namespace std;
const int inf=3005;
const int maxn=802;
int n,m,q,sum[maxn][maxn],ansmax,ansmin;
struct node_y{short maxx,minn,l,r;};
struct node_x{node_y f[maxn<<2];short l,r;}a[maxn<<2];
short max(short a,short b){return a>b?a:b;}
short min(short a,short b){return a<b?a:b;}
void pushup_y(int x,int v) {
a[v].f[x].maxx=max(a[v].f[x<<1].maxx,a[v].f[x<<1|1].maxx);
a[v].f[x].minn=min(a[v].f[x<<1].minn,a[v].f[x<<1|1].minn);
}
void pushup_x(int x,int v){
a[v].f[x].maxx=max(a[v<<1].f[x].maxx,a[v<<1|1].f[x].maxx);
a[v].f[x].minn=min(a[v<<1].f[x].minn,a[v<<1|1].f[x].minn);
}
void build_y(int x,int left,int right,int v,int lx)
{
a[v].f[x].l=left; a[v].f[x].r=right;
if(left==right) {
if(lx!=-1) a[v].f[x].maxx=a[v].f[x].minn=sum[lx][left];
else pushup_x(x,v);
return;
}
int mid=(left+right)>>1;
build_y(x<<1,left,mid,v,lx); build_y(x<<1|1,mid+1,right,v,lx);
pushup_y(x,v);
}
void build_x(int x,int left,int right)
{
a[x].l=left; a[x].r=right;
if(left==right) {build_y(1,1,m,x,left); return;}
int mid=(left+right)>>1;
build_x(x<<1,left,mid); build_x(x<<1|1,mid+1,right);
build_y(1,1,m,x,-1);
}
void query_y(int x,int left,int right,int v)
{
if(a[v].f[x].r<left||a[v].f[x].l>right) return;
if(left<=a[v].f[x].l&&right>=a[v].f[x].r){
ansmax=max(ansmax,a[v].f[x].maxx);
ansmin=min(ansmin,a[v].f[x].minn);
return;
}
query_y(x<<1,left,right,v); query_y(x<<1|1,left,right,v);
}
void query_x(int x,int xl,int xr,int yl,int yr)
{
if(a[x].r<xl||a[x].l>xr) return;
if(xl<=a[x].l&&xr>=a[x].r){query_y(1,yl,yr,x); return;}
query_x(x<<1,xl,xr,yl,yr); query_x(x<<1|1,xl,xr,yl,yr);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) scanf("%d",&sum[i][j]);
build_x(1,1,n);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
scanf("%d",&q);
while(q--)
{
char f[5]; int t1,t2,t3,t4; scanf("%s%d%d%d%d",&f,&t1,&t2,&t3,&t4); ++t1;++t2;++t3;++t4;
if(f[0]=='S') cout<<sum[t3][t4]-sum[t3][t2-1]-sum[t1-1][t4]+sum[t1-1][t2-1]<<'
';
else if(f[1]=='A') ansmax=-inf,query_x(1,t1,t3,t2,t4),cout<<ansmax<<'
';
else ansmin=inf,query_x(1,t1,t3,t2,t4),cout<<ansmin<<'
';
}
return 0;
}