P1073 · OFFICIAL SOLUTION

P1073 相见欢官方题解

Gioush OJ · P1073 相见欢

【部分分：测试点 1∼31\sim 31∼3】

本题为原创题。
这一档中坐标范围很小。把平面划分成整数单位方格，枚举每个小矩形覆盖的全部方格，并记录每个方格的覆盖次数。
设全部小矩形的外接矩形为 $R$ 。当且仅当 $R$ 内的每个单位方格恰好被覆盖一次，且 $R$ 外没有方格被覆盖时，答案为 Yes。
设坐标范围宽度为 $B$ ，时间复杂度为 $\mathcal O(nB^2)$ ，空间复杂度为 $\mathcal O(B^2)$ 。

【部分分：测试点 4∼74\sim 74∼7】

两个矩形的内部相交，当且仅当它们在横轴、纵轴上的开区间投影都相交。
对矩形 $A,B$ ，分别记横坐标区间为 $(l_A,r_A),(l_B,r_B)$ ，纵坐标区间为 $(d_A,u_A),(d_B,u_B)$ 。内部相交等价于

\begin{aligned} \max(l_A,l_B)&<\min(r_A,r_B),\\ \max(d_A,d_B)&<\min(u_A,u_B). \end{aligned}

枚举每一对矩形，若存在内部相交则直接判为不合法。否则只需继续检查是否存在遗漏。
记小矩形面积和为 $S$ ，外接矩形面积为 $S_R$ 。已经确认内部两两不交时，小矩形并集的面积恰为 $S$ 。
所有小矩形都位于 $R$ 内，因此 $S\leq S_R$ 。若 $S=S_R$ ，并集与 $R$ 的面积相同，便不存在正面积的空缺。
所有边界均平行于坐标轴，若存在未覆盖点，则其附近一定含有一个未覆盖的小矩形区域，面积为正，与 $S=S_R$ 矛盾。
时间复杂度为 $\mathcal O(n^2)$ ，空间复杂度为 $\mathcal O(1)$ 。

【部分分：测试点 8∼118\sim 118∼11】

将所有矩形的左右边界离散化为 $X_1<X_2<\cdots<X_p$ ，上下边界离散化为 $Y_1<Y_2<\cdots<Y_q$ 。
任意两条相邻横坐标与相邻纵坐标围成一个最小矩形。原矩形对这些最小矩形的覆盖情况是完整的，不会从中间切开它们。
对离散网格做二维差分。每个原矩形只产生四次修改，恢复前缀和后即可得到每个最小矩形的覆盖次数。
检查外接矩形内覆盖次数是否都为 $1$ 。时间复杂度为 $\mathcal O(n+pq)$ ，空间复杂度为 $\mathcal O(pq)$ 。

【部分分：测试点 12∼1512\sim 1512∼15】

特殊性质已经保证任意两个小矩形的内部互不相交，重叠问题不再需要检查。
计算外接矩形 $R$ 与面积和 $S$ 。若 $S=S_R$ ，根据前面的面积论证，不可能再存在空缺。
因而本档只需一次扫描，时间复杂度为 $\mathcal O(n)$ ，空间复杂度为 $\mathcal O(1)$ 。
完整数据中不能预先排除重叠。面积相等仍然不够，因为一块重叠区域和一块等面积空缺会相互抵消。

【正解】

面积负责检查总量。还需要一个条件检查局部边界是否能严丝合缝地消失。
对每个小矩形的四个角点进行异或式统计。角点第一次出现时放入集合，第二次出现时从集合删除，之后继续交替。
换句话说，集合中只保存出现次数为奇数的角点。
若小矩形恰好拼成外接矩形，内部角点与外接边上的非顶点都会成对出现，最终只剩外接矩形的四个顶点。
记外接矩形四角组成的集合为

C_R=\{(x_{\min},y_{\min}),(x_{\min},y_{\max}), (x_{\max},y_{\min}),(x_{\max},y_{\max})\}.

完整判定条件为

S=S_R \qquad\text{且}\qquad C=C_R,

其中 $C$ 是所有小矩形角点异或后的集合。

两个条件缺一不可。只检查面积无法发现“重叠抵消空缺”，只检查角点也无法排除某些重复覆盖。
下面说明充分性。把所有小矩形的边界叠加在一起。若内部存在空缺或重叠区域，那么该异常区域的边界由若干条水平、竖直线段组成。
异常边界的转折点会使某个非外接角点出现奇数次，或者使外接矩形的某个角点奇偶性错误，因此无法得到 $C=C_R$ 。
角点条件排除了局部边界异常，面积条件又保证总覆盖量等于外接矩形面积，所以覆盖既没有遗漏，也没有重叠。
使用有序集合时，时间复杂度为 $\mathcal O(n\log n)$ ，空间复杂度为 $\mathcal O(n)$ 。使用哈希集合可以得到期望 $\mathcal O(n)$ 时间。

【参考代码】

1/*2Author:Ehundategh3Date:2026/8/264Name:reunion.cpp5You steal,I kill.6*/7#include <set>8#include <cstdio>9#include <algorithm>10using namespace std;11 12int T,n;13 14void Change(set<pair<int,int> > &S,int x,int y){15    pair<int,int> Now={x,y};16    if(S.find(Now)==S.end()) S.insert(Now);17    else S.erase(Now);18}19 20void Solve(){21    int x1,y1,x2,y2;22    int MinX=0x3f3f3f3f,MinY=0x3f3f3f3f;23    int MaxX=-0x3f3f3f3f,MaxY=-0x3f3f3f3f;24    long long Sum=0;25    set<pair<int,int> > S;26    scanf("%d",&n);27    for(int i=1;i<=n;i++){28        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);29        MinX=min(MinX,x1);MinY=min(MinY,y1);30        MaxX=max(MaxX,x2);MaxY=max(MaxY,y2);31        Sum+=1ll*(x2-x1)*(y2-y1);32        Change(S,x1,y1);Change(S,x1,y2);33        Change(S,x2,y1);Change(S,x2,y2);34    }35    bool Tag=Sum==1ll*(MaxX-MinX)*(MaxY-MinY)&&S.size()==4;36    Tag&=S.count({MinX,MinY})&&S.count({MinX,MaxY});37    Tag&=S.count({MaxX,MinY})&&S.count({MaxX,MaxY});38    puts(Tag?"Yes":"No");39}40 41int main(){42    int c;43    scanf("%d%d",&c,&T);44    while(T-->0) Solve();45    return 0;46}