Brief description:
在一个 N*M 的矩阵中寻找一个 A*B 的子矩阵，在这个 A*B 阶的矩阵中再寻找一个 C*D 的子矩阵，
使得这两个矩阵的差最大，另、C*D 子矩阵不可以触碰 A*B 矩阵的边界。
( .. N ≤ 1000 … ）
Analysis:
枚举一阶子矩阵，对二阶子矩阵和每列，分别维护单调队列，时间复杂度 O(NM)。
const int N = 1001;
struct MonoList{
int a[N], b[N];
int op, cz, nn;
inline int size(){
return op - cz + 1;
}
inline int front(){
return a[cz];
}
void init(){
a[0] = 0, op = -1, cz = 0;
}
void init(int l){
a[0] = 0, op = -1, cz = 0, nn = l;
}
void push_without_pop(int val, int label){
while (op >= cz && val <= a[op]){
--op;
}
a[++op] = val, b[op] = label;
}
void push(int val, int label){
push_without_pop(val, label);
if (b[cz] + nn == b[op]) ++cz;
}
} Sub, Col[N];
int _T[101], s[N][N], ans;
int n0, m0, n1, m1, n2, m2;
inline int s1(int x, int y){
return s[x][y] - s[x-n1][y] - s[x][y-m1] + s[x-n1][y-m1];
}
inline int s2(int x, int y){
return s[x][y] - s[x-n2][y] - s[x][y-m2] + s[x-n2][y-m2];
}
int main(){
REP_1(i, 100) _T[i] = (i * 71 + 17) % 100 + 1; Rush{
RD(n0, m0, n1, m1, n2, m2);
REP_1(i, n0) {
int t; RD(t), s[i][1] = s[i-1][1] + t;
FOR_1(j, 2, m0){
t = _T[t];
s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + t;
}
}
ans = 0; FOR(j, m2+1, m0) Col[j].init(n1 - n2 - 1);
Sub.init(m1 - m2 - 1);
FOR(i, n2+1, n1-1) FOR(j, m2+1, m0)
Col[j].push_without_pop(s2(i, j), i);
FOR_1(i, n1, n0){
FOR(j, m2+1, m0) Col[j].push(s2(i-1, j), i-1);
Sub.init(); FOR(j, m2+1, m1) Sub.push_without_pop(Col[j].front(), j);
FOR(j, m1, m0) {
checkMax(ans, s1(i, j) - Sub.front());
Sub.push(Col[j].front(), j);
}
checkMax(ans, s1(i, m0) - Sub.front());
}
OT(ans);
}
}
