题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static int n;
static int m;
static int a;
static int b;
static int N=1010;
static int M=1000010;
static int[][]nums=new int[N][N];
static int[]q=new int[N];
static int[][]result1=new int[N][N];
static int[][]result2=new int[N][N];
static int[][]lastresult1=new int[N][N];
static int[][]lastresult2=new int[N][N];
static int mod=998244353;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
a=sc.nextInt();
b=sc.nextInt();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
nums[i][j]=sc.nextInt();
}
}
for(int i=1;i<=n;i++){
int tt=-1;
int hh=0;
for( int j=1;j<=m;j++){
if(hh<=tt&&-q[hh]+q[tt]+1>=b){
hh++;
}
while (hh<=tt&&nums[i][q[tt]]>=nums[i][j]){
tt--;
}
q[++tt]=j;
if(j>=b){
result1[i][j]=nums[i][q[hh]];
}
}
}
for(int i=1;i<=n;i++){
int tt=-1;
int hh=0;
for( int j=1;j<=m;j++){
if(hh<=tt&&-q[hh]+q[tt]+1>=b){
hh++;
}
while (hh<=tt&&nums[i][q[tt]]<=nums[i][j]){
tt--;
}
q[++tt]=j;
if(j>=b){
result2[i][j]=nums[i][q[hh]];
}
}
}
/* for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
System.out.print(result1[i][j]+" ");
}
System.out.println();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
System.out.print(result2[i][j]+" ");
}
System.out.println();
}*/
for(int i=b;i<=m;i++){
int tt=-1;
int hh=0;
for(int j=1;j<=n;j++){
if(hh<=tt&&-q[hh]+q[tt]+1>=a){
hh++;
}
while (hh<=tt&&result1[q[tt]][i]>=result1[j][i]){
tt--;
}
q[++tt]=j;
if(j>=a){
lastresult1[j][i]=result1[q[hh]][i];
}
}
}
for(int i=b;i<=m;i++){
int tt=-1;
int hh=0;
for(int j=1;j<=n;j++){
if(hh<=tt&&-q[hh]+q[tt]+1>=a){
hh++;
}
while (hh<=tt&&result2[q[tt]][i]<=result2[j][i]){
tt--;
}
q[++tt]=j;
if(j>=a){
lastresult2[j][i]=result2[q[hh]][i];
}
}
}
/* for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
System.out.print(lastresult1[i][j]+" ");
}
System.out.println();
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
System.out.print(lastresult2[i][j]+" ");
}
System.out.println();
}*/
long ans=0;
for(int i=a;i<=n;i++){
for(int j=b;j<=m;j++){
ans=((((long) lastresult1[i][j])*lastresult2[i][j]%mod)+ans)%mod;
}
}
System.out.println(ans);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla