P9514题解

EXODUS · 2023-08-11 23:44:21 · 题解

Part 1：前言

CNOI 風味の強い日本名物！

这要放 CNOI 高低得给你套点超级数据结构，就题而言这道题还是挺不错的/kx。

Part 2：正文

下文中令 d=D,n=N,m=M。

不妨从部分分入手。由于子任务 1 和该题正解做法关联性较低，故不再赘述，我们从子任务 2 开始看起。

我们先偷看一眼样例解释，发现第一种纪念品是一堆相邻最近点对距离为 D 的点阵，第二种则是一个以若干条相邻之间距离为 D 的水平线和竖直线构成的网格，因此不难想到如果我们把平面划分为若干个大小为 D\times D 的方形，每个方形内部都是一样的。故我们只需要考虑任意一个大小为 2D\times 2D 的方形即可（不是 D\times D 的原因是因为选超过边界的答案可能更优）。

因此我们有了一个 O(d^4(n+m)) 的暴力做法。具体而言是枚举每一个矩形和纪念品，判断其是否在这个矩形中即可。

然后我们想起来了我们在噗叽组的时候学过的最大子矩形之类的题目，我们现在试图去枚举三个边界，然后考虑每个纪念品是否已经被包含在当前矩形里。每个纪念品都会对下一个边界产生一个不等式的限制条件，对这些不等式求交即可获得一个 O(d^3(n+m)) 的做法。

我们试着再少扫一个边界，如果你像我一样只扫左上边界的话，你会获得一个没有前途的答辩 O(d^2m) 的做法。因此我们考虑只扫左右边界。我们将纵轴看作是一个环，考虑此时的限制条件是什么。对于每一个一类纪念品，其相当于要求上下边界构成的弧包含其纵坐标。对于每一个二类纪念品，如果当前没有竖直线与其相交，则也是一个和一类纪念品一样的区间限制。这其实是一个环上的覆盖问题，可以以和环长线性相关的复杂度求出。具体而言，我们每次枚举相邻两个点，计算覆盖除去其中间一段的所有位置的答案。时间复杂度 O(d^2(d+n+m))。

再少扫一个边界感觉就彻底没救了。我们现在试图把固定左端点扫一轮右端点的复杂度降低为 O(d+n+m)，即把枚举并计算答案的复杂度均摊出去。不妨倒序枚举右端点，维护当前的每一个限制点。这其实相当于是加入若干关键点然后统计答案的问题。可以通过链表，每次删去一个点后用前驱后继的答案更新答案即可做到单次删除均摊 O(1)。总时间复杂度 O(d(d+n+m))。

那么最后的做法就呼之欲出了。注意到对于每一个位置其实只需要有一个未被覆盖的就需要从链表中被删除。而在所有这样的纪念品中对每一列保留行号最靠右的即可，那么每次均摊的东西由 O(n+m) 变成了 O(d)，所以总时间复杂度是 O(d^2)。

Part 3：代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i(l);i<=(r);++i)
#define per(i,r,l) for(int i(r);i>=(l);--i)
#define eb emplace_back
#define Debug(...) fprintf(stderr,__VA_ARGS__)
int read(){
    int ans=0,flg=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans*flg;
}
template<typename T>
void read(T &x){
    x=0;T flg=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flg=-1;ch=getchar();}
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    x*=flg;
}
template<typename T,typename... Args>
void read(T &x,Args &...args){read(x),read(args...);}

const int N=5e5+7,D=5e3+7;

int n,m,d,P[N],Q[N],R[N],S[N],lst[D][D*2];
bool visx[D],visy[D];
vector<int>vu[D*2];

struct List{
    int pre[N],nxt[N],hd,tl,len;
    void build(){for(int i=0;i<d;i++)pre[i]=i-1,nxt[i]=i+1;hd=0,tl=d-1,len=1e9;}
    void del(int x){
        int l=pre[x],r=nxt[x];
        if(l!=-1)nxt[l]=r;
        if(r!=d)pre[r]=l;
        if(pre[r]==-1)hd=r;
        if(nxt[l]==d)tl=l;
        if(l!=-1&&r!=d)len=min(len,d-(r-l)+1);
    }
}lis;

int main(){
    read(n,m,d);
    rep(i,1,n)read(P[i],Q[i]);
    rep(i,1,m)read(R[i],S[i]);
    rep(i,1,n)visx[P[i]]=1,visy[Q[i]]=1;
    rep(i,1,m)lst[S[i]][R[i]]=R[i],lst[S[i]][R[i]+d]=R[i]+d;
    rep(i,0,d-1)rep(j,1,2*D-1)lst[i][j]=max(lst[i][j-1],lst[i][j]);
    int ans=1e9;
    rep(l,0,d){
        lis.build();int bg=0;
        per(r,l-1+d,0)if(visx[r%d]){bg=r;break;}
        rep(i,0,d-1)if(!visy[i]){
            if(lst[i][l-1+d]<bg)lis.del(i);
            else vu[lst[i][l-1+d]].eb(i);
        }
        rep(r,bg,l-1+d){
            for(auto x:vu[r])lis.del(x);
            ans=min(ans,(r-l+1)*min(lis.len,(lis.tl-lis.hd+1)));
            vu[r].clear();
        }
    }
    printf("%d\n",ans);
    return 0;
}