# 2. 题解

#include <bits/stdc++.h>

#define DS (2)
#define NS (1005)
#define INF (1000000005)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c));
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int A, B, n, root, sz, D, ans = INT_MAX;

struct N
{
int d[DS], mnd, mxd, data, mn[DS], mx[DS], l, r;
int& operator [] (const int a){return d[a];}
}arr[NS * NS], e[NS * NS];

bool cmp(N a, N b){return a[D] < b[D];}

void pup(int a)
{
int l = e[a].l, r = e[a].r;
if (l)
{
e[a].mnd = min(e[a].mnd, e[l].mnd);
e[a].mxd = max(e[a].mxd, e[l].mxd);
}
if (r)
{
e[a].mnd = min(e[a].mnd, e[r].mnd);
e[a].mxd = max(e[a].mxd, e[r].mxd);
}
for (int i = 0; i < DS; i += 1)
{
e[a].mn[i] = e[a].mx[i] = e[a][i];
if (l)
{
e[a].mn[i] = min(e[a].mn[i], e[l].mn[i]);
e[a].mx[i] = max(e[a].mx[i], e[l].mx[i]);
}
if (r)
{
e[a].mn[i] = min(e[a].mn[i], e[r].mn[i]);
e[a].mx[i] = max(e[a].mx[i], e[r].mx[i]);
}
}
}

int Build(int l, int r, int d = 0)
{
if (l > r) return 0;
D = d;
int mid = ((l + r) >> 1), a = ++sz;
nth_element(arr + l, arr + mid, arr + r + 1, cmp);
e[a] = arr[mid];
e[a].l = Build(l, mid - 1, d ^ 1);
e[a].r = Build(mid + 1, r, d ^ 1);
pup(a); return a;
}

bool jud_in(int x1, int y1, int x2, int y2, int a)
{
return x1 <= e[a].mn[0] && y1 <= e[a].mn[1] \
&& x2 >= e[a].mx[0] && y2 >= e[a].mx[1];
}

bool jud_out(int x1, int y1, int x2, int y2, int a)
{
return x1 > e[a].mx[0] || y1 > e[a].mx[1] \
|| x2 < e[a].mn[0] || y2 < e[a].mn[1];
}

bool jud_point(int x1, int y1, int x2, int y2, int a)
{
return x1 <= e[a][0] && y1 <= e[a][1] \
&& x2 >= e[a][0] && y2 >= e[a][1];
}

void jud_res(PII& res, PII a)
{
res.FIR = min(res.FIR, a.FIR), res.SEC = max(res.SEC, a.SEC);
}

PII query(int x1, int y1, int x2, int y2, int a = root)
{
if (!a) return PII(INF, -INF);
if (jud_in(x1, y1, x2, y2, a)) return PII(e[a].mnd, e[a].mxd);
if (jud_out(x1, y1, x2, y2, a)) return PII(INF, -INF);
PII res(INF, -INF);
if (jud_point(x1, y1, x2, y2, a))
jud_res(res, PII(e[a].data, e[a].data));
jud_res(res, query(x1, y1, x2, y2, e[a].l));
jud_res(res, query(x1, y1, x2, y2, e[a].r));
return res;
}

int main (int argc, char const* argv[])
{
IN(A), IN(B), IN(n);
for (int i = 1, k, tot = 1; i <= A; i += 1)
for (int j = 1; j <= B; j += 1)
IN(k), arr[tot++] = (N){i, j, k, k, k};
root = Build(1, A * B);
for (int i = 1; i <= A - n + 1; i += 1)
for (int j = 1; j <= B - n + 1; j += 1)
{
PII tmp = query(i, j, i + n - 1, j + n - 1);
ans = min(ans, tmp.SEC - tmp.FIR);
}
printf("%d\n", ans);
return 0;
}


$$mx[i,j]=MAX(a[i,k]|k\in [j,j+n-1])$$
$$mn[i,j]=MIN(a[i,k]|k\in [j,j+n-1])$$

$$max[i,j]=MAX(mx[k,j]|k\in [i,i+n-1])$$
$$min[i,j]=MIN(mn[k,j]|k\in [i,i+n-1])$$

BZOJ 上可以直接过，6s

luogu 上的话时间严格些，需要开 O2 才能过

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define NS (1005)

using namespace std;
using namespace __gnu_pbds;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c));
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int A, B, n, mp[NS][NS], ans = INT_MAX, mx[NS][NS], mn[NS][NS];

cc_hash_table<int,int> hmx, hmn;

priority_queue<int> qmx;

priority_queue<int, vector<int>, greater<int> > qmn;

int main (int argc, char const* argv[])
{
IN(A), IN(B), IN(n);
for (int i = 1; i <= A; i += 1)
for (int j = 1; j <= B; j += 1)
IN(mp[i][j]);
for (int i = 1; i <= A; i += 1)
{
while (!qmx.empty()) qmx.pop();
while (!qmn.empty()) qmn.pop();
hmx.clear(), hmn.clear();
for (int j = 1; j <= n; j += 1) qmx.push(mp[i][j]), qmn.push(mp[i][j]);
for (int j = 1; j + n - 1 <= B; j += 1)
{
while (hmx[qmx.top()] > 0) hmx[qmx.top()]--, qmx.pop();
while (hmn[qmn.top()] > 0) hmn[qmn.top()]--, qmn.pop();
mx[i][j] = qmx.top(), mn[i][j] = qmn.top();
qmx.push(mp[i][j + n]), hmx[mp[i][j]]++;
qmn.push(mp[i][j + n]), hmn[mp[i][j]]++;
}
}
for (int i = 1; i + n - 1 <= B; i += 1)
{
while (!qmx.empty()) qmx.pop();
while (!qmn.empty()) qmn.pop();
hmx.clear(), hmn.clear();
for (int j = 1; j <= n; j += 1) qmx.push(mx[j][i]), qmn.push(mn[j][i]);
for (int j = 1; j + n - 1 <= A; j += 1)
{
while (hmx[qmx.top()] > 0) hmx[qmx.top()]--, qmx.pop();
while (hmn[qmn.top()] > 0) hmn[qmn.top()]--, qmn.pop();
ans = min(ans, qmx.top() - qmn.top());
qmx.push(mx[j + n][i]), hmx[mx[j][i]]++;
qmn.push(mn[j + n][i]), hmn[mn[j][i]]++;
}
}
printf("%d\n", ans);
return 0;
}


# Update

QvQ

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c));
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}

int A, B, n, mp[NS][NS], ans = INT_MAX, mx[NS][NS], mn[NS][NS];

struct N
{
int d, t;
bool operator < (N a) const {return d < a.d;}
bool operator > (N a) const {return d > a.d;}
};

template <typename _Tp, typename _Cmp = less<_Tp> > struct que
{
_Tp d[NS]; int head, tail; _Cmp cmp;
void init(){head = tail = 1;}
void push(_Tp a)
{
while (head < tail && cmp(a, d[tail - 1])) tail--;
d[tail++] = a;
}
};

que <N, greater<N> > qmx;
que <N, less<N> > qmn;

int main (int argc, char const* argv[])
{
IN(A), IN(B), IN(n);
for (int i = 1; i <= A; i += 1)
for (int j = 1; j <= B; j += 1)
IN(mp[i][j]);
for (int i = 1; i <= A; i += 1)
{
qmx.init(), qmn.init();
for (int j = 1; j <= n; j += 1)
qmx.push((N){mp[i][j], j}), qmn.push((N){mp[i][j], j});
for (int j = 1; j + n -1 <= B; j += 1)
{
while (qmx.top().t < j) qmx.pop();
while (qmn.top().t < j) qmn.pop();
mx[i][j] = qmx.top().d, mn[i][j] = qmn.top().d;
qmx.push((N){mp[i][j + n], j + n});
qmn.push((N){mp[i][j + n], j + n});
}
}
for (int i = 1; i + n - 1 <= B; i += 1)
{
qmx.init(), qmn.init();
for (int j = 1; j <= n; j += 1)
qmx.push((N){mx[j][i], j}), qmn.push((N){mn[j][i], j});
for (int j = 1; j + n - 1 <= A; j += 1)
{
while (qmx.top().t < j) qmx.pop();
while (qmn.top().t < j) qmn.pop();
ans = min(ans, qmx.top().d - qmn.top().d);
qmx.push((N){mx[j + n][i], j + n});
qmn.push((N){mn[j + n][i], j + n});
}
}
printf("%d\n", ans);
return 0;
}


### 7 条评论

#### konnyakuxzy · 2018年2月10日 10:50 下午

ST 表好像是可以的
但是
我。。。
可能不会
（我写过的那种 RMQ 貌似是预处理要 $O(nlog_2n)$的啊）
真是让人因式分解 QvQ
树状数组的话就不清楚了 QvQ
您是打算用树状数组维护区间最小咩？
那玩意貌似是 $log_2^2$的吧

#### boshi · 2018年2月11日 1:43 下午

哦似的似的 $log^2n$，貌似迪卡尔树可以把 RMQ 搞成 O(n) 的虽然我也不懂

#### TPLY · 2018年2月8日 2:08 下午

#include
#define INF 2147483647
#define SZ 1001

using namespace std;

int a,b,n,ans=INF,l1,r1,l2,r2;
int q1[SZ],q2[SZ],s[SZ][SZ],mx[SZ][SZ],mn[SZ][SZ];

int main()
{
scanf("%d%d%d",&a,&b,&n);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
scanf("%d",&s[i][j]);

for(int i=1;i<=a;i++)
{
l1=l2=1,r1=r2=0;  //1: 最大 2: 最小
for(int j=1;j<=b;j++)
{
while(l1<=r1&&s[i][q1[r1]]<=s[i][j]) r1--;
while(l2<=r2&&s[i][q2[r2]]>=s[i][j]) r2--;
q1[++r1]=j;q2[++r2]=j;
while(l1<=r1&&q1[l1]<j-n+1) l1++;
while(l2<=r2&&q2[l2]<j-n+1) l2++;
if(j>=n)
{
mx[i][j-n+1]=s[i][q1[l1]];
mn[i][j-n+1]=s[i][q2[l2]];
}
}
}

for(int i=1;i<=b-n+1;i++)
{
l1=l2=1,r1=r2=0;
for(int j=1;j<=a;j++)
{
while(l1<=r1&&mx[q1[r1]][i]<=mx[j][i]) r1--;
while(l2<=r2&&mn[q2[r2]][i]>=mn[j][i]) r2--;
q1[++r1]=j;q2[++r2]=j;
while(l1<=r1&&q1[l1]<j-n+1) l1++;
while(l2<=r2&&q2[l2]<j-n+1) l2++;
if(j>=n)
{
ans=min(ans,mx[q1[l1]][i]-mn[q2[l2]][i]);
}
}
}

printf("%d",ans);

return 0;
}


#### konnyakuxzy · 2018年2月8日 2:48 下午

诶，好像是的诶！
貌似没有必要用优先队列的说！
可以把复杂度降到 $O(AB)$吧
我这就去试试 QvQ
我太蠢了.jpg
（还有您那个，，，原来评论的代码有问题我帮您改好了）

#### konnyakuxzy · 2018年2月8日 3:44 下午

Orz 我也实现单调队列啦 QvQ
已经更新文章啦 QvQ