Description
题目背景 热烈庆祝北京师范大学附属实验中学成立100周年! 问题描述 为了准备校庆庆典,学校招募了一些学生组成了一个方阵,准备在庆典上演出。 这个方阵是一个n*m的矩形,第i行第j列有一名学生,他有一个能力值Aij。 校长会定期检查一个p*q的方阵,询问这个方阵的学生能力值之和,或是学生能力值的最大值,或是学生能力值的最小值。由于校长不喜欢一个方阵长宽之比差太多,他每次询问的方阵的长不会超过宽的两倍。作为校庆筹办组组长的你,应该迅速并准确的回答校长所问的问题。
第一行包含两个整数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
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
样例说明 对于第一组询问,能力值之和为1+2+4+5=12。 对于第二组询问,能力值最大的位置为第2行第2列。 对于第三组询问,能力值最小的位置为第0行第1列。
Data Constraint
对于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, 每个询问的方阵的长不超过宽的两倍
Solution
矩阵和前缀和处理,矩阵最值用二维 RMQ 维护即可。
设
F[i][j][k]
从
(i,j)
向下延伸
2k
、向右延伸
2k
的最大值,最小值同理。
Code
#include<cstdio>
#include<cmath>
using
namespace std;
const
int N=
801;
int a[N][N],sum[N][N],f[N][N][
10],g[N][N][
10],p[
11];
inline
int read()
{
int X=
0,w=
1; char ch=
0;
while(ch<
'0' || ch>
'9') {
if(ch==
'-') w=-
1;ch=getchar();}
while(ch>=
'0' && ch<=
'9') X=(X<<
3)+(X<<
1)+ch-
'0',ch=getchar();
return X
*w;
}
inline
int write(
int x)
{
if(x>
9) write(x/
10);
putchar(x
+
'0');
}
inline
int max(
int x,
int y)
{
return x>y?x:y;
}
inline
int min(
int x,
int y)
{
return x<y?x:y;
}
int main()
{
int n=read(),m=read();
for(
int i=
1;i<=n;i++)
for(
int j=
1;j<=m;j++)
{
f[i][j][
0]=g[i][j][
0]=a[i][j]=read();
sum[i][j]=sum[i-
1][j]+sum[i][j-
1]-sum[i-
1][j-
1]+a[i][j];
}
for(
int i=p[
0]=
1;i<=
10;i++) p[i]=p[i-
1]<<
1;
for(
int k=
1;k<
10;k++)
for(
int i=
1;i<=n && i+p[k]-
1<=n;i++)
for(
int j=
1;j<=m && j+p[k]-
1<=m;j++)
{
f[i][j][k]=
max(f[i][j][k-
1],f[i][j+p[k-
1]][k-
1]);
f[i][j][k]=
max(f[i][j][k],
max(f[i+p[k-
1]][j][k-
1],f[i+p[k-
1]][j+p[k-
1]][k-
1]));
g[i][j][k]=
min(g[i][j][k-
1],g[i][j+p[k-
1]][k-
1]);
g[i][j][k]=
min(g[i][j][k],
min(g[i+p[k-
1]][j][k-
1],g[i+p[k-
1]][j+p[k-
1]][k-
1]));
}
int q=read();
while(q--)
{
char ch=getchar();
while(ch!=
'X' && ch!=
'N' && ch!=
'U') ch=getchar();
int x1=read()+
1,y1=read()+
1,x2=read()+
1,y2=read()+
1;
if(ch==
'U')
{
write(sum[x2][y2]-sum[x2][y1-
1]-sum[x1-
1][y2]+sum[x1-
1][y1-
1]),putchar(
'\n');
continue;
}
int ans=ch==
'N'?
3000:
0,z=
min(log2(x2-x1+
1),log2(y2-y1+
1));
if(ch==
'X')
{
for(
int yy=y1;yy+p[z]<=y2;yy+=p[z]) ans=
max(ans,
max(f[x1][yy][z],f[x2-p[z]+
1][yy][z]));
for(
int xx=x1;xx+p[z]<=x2;xx+=p[z]) ans=
max(ans,
max(f[xx][y1][z],f[xx][y2-p[z]+
1][z]));
ans=
max(ans,
max(f[x1][y1][z],f[x1][y2-p[z]+
1][z]));
ans=
max(ans,
max(f[x2-p[z]+
1][y1][z],f[x2-p[z]+
1][y2-p[z]+
1][z]));
}
else
{
for(
int yy=y1;yy+p[z]<=y2;yy+=p[z]) ans=
min(ans,
min(g[x1][yy][z],g[x2-p[z]+
1][yy][z]));
for(
int xx=x1;xx+p[z]<=x2;xx+=p[z]) ans=
min(ans,
min(g[xx][y1][z],g[xx][y2-p[z]+
1][z]));
ans=
min(ans,
min(g[x1][y1][z],g[x1][y2-p[z]+
1][z]));
ans=
min(ans,
min(g[x2-p[z]+
1][y1][z],g[x2-p[z]+
1][y2-p[z]+
1][z]));
}
write(ans),putchar(
'\n');
}
return 0;
}