赞
踩
那个大佬知道是哪里错了呀
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class _2020_6线段树 {
static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
static int n, m, lim, ans = 0;
static int nus = 100007;
static int[] maxt = new int[4 * nus];
static int[] mint = new int[4 * nus];
static int[] max = new int[nus];
static int[] min = new int[nus];
static int[][] arr = new int[101][100007];
public static void main(String[] args)throws Exception {
String s[] = bf.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
for(int i = 1; i <= n; i++) {
s = bf.readLine().split(" ");
for(int j = 1; j <= m; j++) {
arr[i][j] = Integer.parseInt(s[j - 1]);
}
}
lim = Integer.parseInt(bf.readLine());
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
ans = Math.max(ans, cal(i, j));
}
}
System.out.println(ans);
}
private static int cal(int u, int d) {
int ans1 = 0;
for(int i = 1; i <= m; i++) {
int ma = 0 , mi = (int)1e9;
for(int j = u; j <= d; j++) {
ma = Math.max(ma , arr[j][i]);
mi = Math.min(mi , arr[j][i]);
}
max[i] = ma;
min[i] = mi;
}
build(1, 1, m);
int r = 1;
for(int l = 1; l <= m; l++){
while(r <= m && queryma(1, 1, m, l, r) - querymi(1, 1, m, l, r) <= lim){
r ++;
}
ans1 = Math.max(ans1 , (d - u + 1) * (r - l));
}
return ans1;
}
public static void build(int f, int l, int r) {
if(l == r) {
maxt[f] = max[l];
mint[f] = min[l];
return;
}
int mid = (l + r) >> 1;
build(f << 1, l, mid);
build(f << 1 | 1, mid + 1, r);
maxt[f] = Math.max(maxt[f << 1], maxt[f << 1 | 1]);
mint[f] = Math.min(mint[f << 1], mint[f << 1 | 1]);
}
public static int queryma(int f, int lt, int rt, int l, int r) {
int res = 0;
if(lt >= l && rt <= r) {
return maxt[f];
}
int mid = ((lt + rt) / 2);
if(l <= mid)
res = Math.max(res, queryma(f << 1, lt, mid, l, r));
if(r > mid)
res = Math.max(res, queryma(f << 1 | 1, mid + 1, rt, l, r));
return res;
}
public static int querymi(int f, int lt, int rt, int l, int r) {
int res = 1000000000;
if(lt >= l && rt <= r) {
return mint[f];
}
int mid = ((lt + rt) / 2);
if(l <= mid)
res = Math.min(res, querymi(f << 1, lt, mid, l, r));
if(r > mid)
res = Math.min(res, querymi(f << 1 | 1, mid + 1, rt, l, r));
return res;
}
}
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。