题解：P9514 [JOI Open 2023] 花园 / Garden

· · 题解

[JOI Open 2023] 花园 / Garden 题解

博客园链接：[JOI Open 2023] 花园 / Garden 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

单调队列。

分析

首先可以看出所有的坐标范围都只需要在 [0,2D) 取到即可。

这类求矩形面积相关的题目有一个套路：枚举左下角，那么它的两维范围是 [0,D)。

A 类比较简单，它的存在只是让我们固定了最小范围，比如一个 (P,Q)，假设现在有一个点 (x,y)，如果它作为矩形左下角，那么右上角 (x',y') 需要满足：

  1. - $x\le P$，$x'\ge P$。 - $x > P$，$x'\ge P+D$。
  2. - $y\le Q$，$y'\ge Q$。 - $y > Q$，$y'\ge Q+D$。

所以 A 类可以开两个 O(D) 的数组 AX_x,AY_y 用前缀最值预处理出来。

B 类其实也一样，对于一个 (R,S)，假设现在有一个点 (x,y)，如果它作为矩形左下角，那么右上角 (x',y') 需要满足以下两个条件的其中一个：

  1. - $x\le R$，$x'\ge R$。 - $x > R$，$x'\ge R+D$。
  2. - $y\le S$，$y'\ge S$。 - $y > S$，$y'\ge S+D$。

现在枚举左下角 (x,y)。

考虑单调队列做法，枚举每个 x 值，O(M) 处理出每个 y 对应的最小 x 值 BX_y：对于一个 (R,S)，我们将其 S 记在 R-1,R+D-1 两个值上，枚举 y 时，我们将它滑动窗口的范围设为 [y,y+D-1)，然后枚举单调队列中的值即可。

那么我们得到了一个 O(D^3+DM) 的算法。

发现每次 O(M) 预处理出的数组有很多重复部分，可以离线，每个 (R,S) 只需在 0,R+1 两个 x 轴坐标分别做两次修改。

然后单调队列中的值只需要在 y 删除的时候与 y-1 做一次更新即可，容易看出这样是最优的，O(D^3) 变为 O(D^2)。

注意有一些边界条件要特殊处理。

总复杂度 O(N+M+D^2)。

代码

constexpr int N(5e5+10),_D(5e3+10);

int n,m,D,ans;
int AX[_D],AY[_D],BX[_D<<1];
vector<int> vec[_D];

int cal(int xa,int xb,int ya,int yb) { return (xb-xa+1)*(yb-ya+1); }

signed main() {
#ifdef plus_cat
    freopen(plus_cat ".in","r",stdin),freopen(plus_cat ".out","w",stdout);
#endif // plus_cat
    /*DE("Input");*/
    scanf("%d%d%d",&n,&m,&D),ans=D*D;
    /*DE("Solve A class");*/
    FOR(i,1,n) {
        int x,y;
        scanf("%d%d",&x,&y);
        tomax(AX[0],x),tomax(AX[x+1],x+D);
        tomax(AY[0],y),tomax(AY[y+1],y+D);
    }
    FOR(i,1,D)tomax(AX[i],i,AX[i-1]),tomax(AY[i],i,AY[i-1]);
    /*DE("Record B class");*/
    FOR(y,0,2*D-1)BX[y]=0;
    FOR(i,1,m) {
        int x,y;
        scanf("%d%d",&x,&y);
        if(y>0)tomax(BX[y-1],x);
        tomax(BX[y+D-1],x),vec[x+1].push_back(y);
    }
    /*DE("Solve");*/
    FOR(x,0,D-1) {
        tomin(ans,cal(x,AX[x],0,D-1));
        for(int y:vec[x]) {
            if(y>0)tomax(BX[y-1],x+D-1);
            tomax(BX[y+D-1],x+D-1);
        }
        int it(0),h(1),t(0);
        static int q[_D<<1];
        auto update=[&](int i,int y) {
            if(y<0)return;
            int _y(max(q[i-1]+1,AY[y]));
            tomin(ans,cal(x,max(AX[x],BX[q[i]]),y,_y));
        };
        FOR(y,0,D-1) {
            while(it<y+D-1) {
                while(h<=t&&BX[it]>BX[q[t]])update(t--,y-1);
                q[++t]=it++;
            }
            while(h<=t&&q[h]<AY[y])update(h++,y-1);
        }
        while(h<=t)update(h++,D-1);
    }
    /*DE("Output");*/
    printf("%d\n",ans);
    return 0;
}