【题解】理想的正方形 堆+哈希表 / 单调队列 BZOJ – 1047

于由XZYQvQ发布

1. 题目

传送门=￣ω￣=

题意：
在一个 $A\times B$的矩阵中找出一个 $N\times N$的矩阵使得该矩阵内最大值与最小值的差值最小。
数据范围 $A,B\leq 10^3,n\leq 10^2$

2. 题解

听说正解是动态规划 QvQ，但我的是暴力堆+哈希表。。。

害怕.jpg

但是我沉迷暴力的数据结构，于是先写了个 kd-tree 版的，然后毫无疑问地 TLE 了

代码如下（会 T 不用试了）

#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]$表示第 $i$行的区间 $[j,j+n-1]$内的最大值。

而 $mn[i,j]$表示第 $i$行的区间 $[j,j+n-1]$内的最小值。

即：
$$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])$$

怎么求 $mx,mn$呢？

不难想到用一颗平衡树维护

首先枚举行数 $i$，然后把第 $i$行的区间 $[1,n]$内的元素丢到平衡树里，这样 $mx[i,1]$就是平衡树中最大的元素，$mn[i,1]$就是平衡树中最小的元素。

接着枚举 $j$，每次将第 $i$行第 $j-1$个元素从平衡树中删除，再向平衡树中添加第 $i$行地 $j+n-1$个元素。然后依然是平衡树中最小的元素是 $mn[i,j]$，最大的是 $mx[i,j]$

求出了 $mn,mx$又有什么用呢？

我们再设 $min[i,j]$为矩形 $(i,j)(i+n,j+n)$（这里给出的两个坐标表示矩形的左上角和右下角）内的最小值，$max[i,j]$表示矩形 $(i,j)(i+n,j+n)$内的最大值

很明显：
$$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])$$

所以求法和求 $mx,mn$是相同的！

用平衡树维护即可

复杂度是 $O(ABlog_2n)$的。

但是我，，，很懒，就不想手打平衡树

然后发现 multiset 很慢（map 也很慢），因为它插入、删除、取最大最小都是很慢的。最大的点开 O2 还要 3s+

所以我们用堆来替换它

搞两个堆，一个大根堆一个小根堆。

至于删除，就搞两个哈系表分别对应两个堆，分别储存某个数字被删除了多少次。如果某次取出的堆顶，发现它被删除次数大于 0, 就直接把它弹掉，并且哈系表中它对应的映射值减一。

就这样可以快很多。

堆我用的是 stl 的优先队列，哈希表用的是 pbds 的 gp_hash_table。

我试了试发现 pbds 里也有优先队列，跑的快一些。但是，，，没有本质上快很多，所以就懒得改了。。。

BZOJ 上可以直接过，6s

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

谁叫我写的暴力呢 QvQ

代码：

#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

这样复杂度就是 $O(AB)$的了

代码：

#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;
    }
    _Tp top(){return d[head];}
    void pop(){head++;}
};

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;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

7 条评论

boshi · 2018年2月10日 10:20 下午

这个能不能用树状数组:O(ABlogN) 或者 RMQ:O(AB) 来搞呢？开了 O2 树状数组应该比较快吧？

回复

    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

    回复

TPLY · 2018年2月8日 2:06 下午

诶诶诶这道题我用单调队列水的诶

回复

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注