学步园

果然我只会做水题233还写了好久

一开始用multisetTLE,结果是BZOJ题面数据范围小了233

然后发现我没有学过单调队列233

固定区间最大/最小值,用单调队列优化至O(n)

这个题先处理出f[i][j]表示(i,j)到(i+n-1,j)的最大/最小值

再用f处理出max/min[i][j]表示(i,j)到(i+n-1,j+n-1)的最大/最小值

然后WA的不能自理然后发现打错了变量名233

Code:(自己YY的单调队列好丑233)

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 1001
int d[N][N], n, m, k;
char c;
int ma[N][N], mi[N][N], ans(0x7fffffff);
int fma[N][N], fmi[N][N];
inline void read(int &x)
{
    int opt(1);
    for (c = getchar();c > '9' || c < '0';c = getchar())
        if (c == '-')opt = -1;
    for (x = 0;c >= '0' && c <= '9';c = getchar())
        x = (x << 3) + (x << 1) + c - '0';
    x *= opt;
}
struct Item
{
    int i, d;
    Item(int _i = 0, int _d = 0){i = _i, d = _d;}
};
struct max_queue
{
    Item q[N];
    int head, tail;
    void push(int i, int x)
    {
        while (head < tail && q[tail-1].d <= x)
            tail--;
        q[tail++] = Item(i, x);
    }
    void clear()
    {
        head = tail = 0;
        q[head] = Item(0, 0);
    }
    int qmax(int l)
    {
        while (head < tail && q[head].i < l)
            head++;
        return q[head].d;
    }
}qma;
struct min_queue
{
    Item q[N];
    int head, tail;
    void push(int i, int x)
    {
        while (head < tail && q[tail-1].d >= x)
            tail--;
        q[tail++] = Item(i, x);
    }
    void clear()
    {
        head = tail = 0;
        q[head] = Item(0, 0);
    }
    int qmin(int l)
    {
        while (head < tail && q[head].i < l)
            head++;
        return q[head].d;
    }
}qmi;
void work()
{
    int i, j;
    for (i = 1;i <= n; ++i)
    {
        qma.clear(), qmi.clear();
        for (j = 1;j < k; ++j)
            qma.push(j, d[i][j]), qmi.push(j, d[i][j]);
        for (j = k;j <= m; ++j)
        {
            qma.push(j, d[i][j]), qmi.push(j, d[i][j]);
            fma[i][j-k+1] = qma.qmax(j-k+1), fmi[i][j-k+1] = qmi.qmin(j-k+1);
        }
    }
    for (j = 1;j <= m; ++j)
    {
        qma.clear(), qmi.clear();
        for (i = 1;i < k; ++i)
            qma.push(i, fma[i][j]), qmi.push(i, fmi[i][j]);
        for (i = k;i <= n; ++i)
        {
            qma.push(i, fma[i][j]), qmi.push(i, fmi[i][j]);
            ma[i-k+1][j] = qma.qmax(i-k+1), mi[i-k+1][j] = qmi.qmin(i-k+1);
        }
    }
    for (i = 1;i + k - 1 <= n; ++i)
        for (j = 1;j + k - 1 <= m; ++j)
            ans = min(ans, ma[i][j] - mi[i][j]);
    printf("%d", ans);
}
int main()
{
    int i, j;
    read(n), read(m), read(k);
    for (i = 1;i <= n; ++i)
        for (j = 1;j <= m; ++j)
            read(d[i][j]);
    work();
}