2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）

题目大意

我们试图设计一个墙壁，将其作为2D矩形砖块形状的镶嵌，所有砖块都具有完全的整数坐标和完全的整数大小。

给定这个2D墙壁上砖块的描述，确定墙壁是否确实是一个墙壁——覆盖一个完美的矩形，没有砖块重叠，砖块之间也没有空白空间。这意味着区域内的每个非整数坐标都应该被一个砖块完全覆盖。

分别说明样本1、2和3的砖块图示。

输入

• 一行，包含砖块数量 $n$ ($1 \le n \le 1\,000\,000$)。

• $n$ 行，每行描述一个砖块，包括四个整数 $x \ y\ w\ h$ 分别表示 xy 坐标、宽度、高度 ($0 \le x, y \le 10^8$; $1 \le w, h \le 10^8$)。

说白了就是这个砖块的位置，还有长宽都告诉你了。呃，但是呢这个砖块的的这个长宽，还有数量比较大。需要你判断一下这些砖块之间有没有重叠。

思路讲解

一言以蔽之，我们这道题目所采用的策略就是维护一个在当前激活的 X 区间上的不相交的 Y 区间集合。也就是说，我们的这个 activates 集合，它里面存储的是 y 区间。然后 activates 的进出是使用的 event 去控制，去顺序遍历 event 以控制 activates 里面的y 区间集合的进出。

其实扫描线思想的精髓呢，其实就是把二维的问题看成是一维的问题，通过消除偏序关系，维护激活集合。**维护激活的矩形集合。**等方式。

如果说我们维护一个集合，这个集合当中只有当前还生效的矩形，我们是不是会轻松很多？

呃，我们先使用event类来模拟这个矩形的进入和删除。

struct Event {
    ll x,y_st,y_ed,op;
    bool operator<(const Event & o) const {
        if (x!=o.x) return x<o.x;
        return op<o.op;

    }
    // auto operator<=>(const Event &)const =default;
};
    multiset<Event> event_st;
    for (int i=0;i<N;++i) {
        ll x,y,w,h;
        cin>>x>>y>>w>>h;
        mnx=min(mnx,x);
        mny=min(mny,y);
        mxx=max(mxx,x+w);
        mxy=max(mxy,y+h);
        acc_area+=w*h;
        // rect_ls[i]={x,y,w,h};
        event_st.insert({x,y,y+h,1});
        event_st.insert({x+w,y,y+h,0});
    }

然后我们去读取 event 类去模拟这个进入和删除的过程，保持 activates 这个Pair set里面只有这个，已经激活的矩形，那么已经激活的矩形其实就相当于一段线段了（在Y方向上的线段）。我们使用check函数去检查一下，就是我们插入的这个东西，它会不会呃和activs里面本来就有的这个线段重叠（不过，因为activates里面的这个所有的线段都是互不重叠的，所以说判断起来会非常容易，只需要检查前驱和后继即可。）。

// 如果假设 activates 是这个互不重叠的，那么肯定没问题
set<pair<ll,ll>> activates;
for (auto &event:event_st) {
    auto [x,y_st,y_ed,op]=event;
    if (op==1) {
        if (!check({y_st,y_ed})) {
            cout<<"no\n";
            return;
        }
        activates.insert({y_st,y_ed});
    }else {
        activates.erase({y_st,y_ed});
    }
}
cout<<"yes\n";

auto check=[&](pair<ll,ll> y_pair) -> bool {
    if (activates.empty()) {
        return true;
    }
    auto it=activates.upper_bound(y_pair);
    if (it!=activates.end()) {
        if (y_pair.first>=it->second || y_pair.second<=it->first) {

        }else {
            return false;
        }
    }
    if (it!=activates.begin()) {
        it=prev(it);
        if (y_pair.first>=it->second || y_pair.second<=it->first) {

        }else {
            return false;
        }
    }
    return true;
};

AC代码

AC
https://qoj.ac/submission/2011619

只能够通过 qoj 数据的错解

/**
 * Problem: B. Brickwork
 * Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106157/problem/B
 * Created: 2026-02-07 00:00:00
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Rectangle {
    ll x,y,w,h;
    bool operator<(const Rectangle &o) const {
        if (x+w!=o.x+o.w) {
            return x+w<o.x+o.w;
        }
        return h+y<o.h+o.y;
    }
};
void Solve() {
    ll N;
    cin >> N;
    ll mnx=INF,mny=INF,mxx=0,mxy=0;
    ll acc_area=0;
    vector<Rectangle> rect_ls(N);
    for (int i=0;i<N;++i) {
        ll x,y,w,h;
        cin>>x>>y>>w>>h;
        mnx=min(mnx,x);
        mny=min(mny,y);
        mxx=max(mxx,x+w);
        mxy=max(mxy,y+h);
        acc_area+=w*h;
        rect_ls[i]={x,y,w,h};
    }
    // 用总面积和这个覆盖面积比，如果不相等，说明一定发生了空缺或者重叠
    if ((mxx-mnx)*(mxy-mny)!=acc_area) {
        cout<<"no\n";
        return;
    }
    // 需要判断各个矩形之间是否有重叠，有重叠输出 no
    // 我们的想法就是先根据 x,y 排序
    // 我们最好使用这个结束位置排序
    sort(all(rect_ls));
    for (int i=1;i<N;++i) {
        auto [x1,y1,w1,h1]=rect_ls[i-1];
        auto [x2,y2,w2,h2]=rect_ls[i];
        if (x2>=x1+w1) {
            continue;
        }
        if (y2>=y1+h1 || y2+h2<=y1) {
            continue;
        }
        cout<<"no\n";
        return;
    }
    cout<<"yes\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://qoj.ac/submission/2011619

*/

AC
https://codeforces.com/gym/106157/submission/361754040

https://qoj.ac/submission/2011657

正解

/**
 * Problem: B. Brickwork
 * Contest: 2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025)
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106157/problem/B
 * Created: 2026-02-07 02:16:01
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
struct Rectangle {
    ll x,y,w,h;
    bool operator<(const Rectangle &o) const {
        if (x+w!=o.x+o.w) {
            return x+w<o.x+o.w;
        }
        return h+y<o.h+o.y;
    }
};
struct Event {
    ll x,y_st,y_ed,op;
    bool operator<(const Event & o) const {
        if (x!=o.x) return x<o.x;
        return op<o.op;

    }
    // auto operator<=>(const Event &)const =default;
};

void Solve() {
    ll N;
    cin >> N;
    ll mnx=INF,mny=INF,mxx=0,mxy=0;
    ll acc_area=0;
    // vector<Rectangle> rect_ls(N);
    multiset<Event> event_st;
    for (int i=0;i<N;++i) {
        ll x,y,w,h;
        cin>>x>>y>>w>>h;
        mnx=min(mnx,x);
        mny=min(mny,y);
        mxx=max(mxx,x+w);
        mxy=max(mxy,y+h);
        acc_area+=w*h;
        // rect_ls[i]={x,y,w,h};
        event_st.insert({x,y,y+h,1});
        event_st.insert({x+w,y,y+h,0});
    }
    // 如果假设 activates 是这个互补重叠的，那么肯定没问题
    set<pair<ll,ll>> activates;
    auto check=[&](pair<ll,ll> y_pair) -> bool {
        if (activates.empty()) {
            return true;
        }
        auto it=activates.upper_bound(y_pair);
        if (it!=activates.end()) {
            if (y_pair.first>=it->second || y_pair.second<=it->first) {

            }else {
                return false;
            }
        }
        if (it!=activates.begin()) {
            it=prev(it);
            if (y_pair.first>=it->second || y_pair.second<=it->first) {

            }else {
                return false;
            }
        }
        return true;
    };
    for (auto &event:event_st) {
        auto [x,y_st,y_ed,op]=event;
        if (op==1) {
            if (!check({y_st,y_ed})) {
                cout<<"no\n";
                return;
            }
            activates.insert({y_st,y_ed});
        }else {
            activates.erase({y_st,y_ed});
        }
    }
    cout<<"yes\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106157/submission/361754040

*/

心路历程（WA，TLE，MLE……）