P5998 [PA2014]Plemiona 题解

· · 题解

P5998 [PA2014]Plemiona 题解

Analysis

很巧妙的东西，终于是胡出来了。

首先，我们对矩形按照操作的 y 值右端点排序。

然后我们考虑用线段树维护 x 轴。

我们发现两个相交的线段所覆盖到的线段树节点上一定有某一对节点呈父子关系，原因显然。

但是在线段树上一个节点的子树太大了，我们考虑用孩子数祖先。

我们给每个线段树节点开 2 个 vector，姑且叫它 vec1 和 vec2。

我们把矩形加入线段树时就加入所有 访问过 的节点的 vec2，并且加入其完全覆盖的最上层节点（也就是我们平时线段树维护区间操作的那些节点）的 vec1。

我们合并矩形时时就计算与 访问过 的节点的 vec1 的矩形是否有交，并且计算其完全覆盖的最上层节点（也就是我们平时线段树维护区间操作的那些节点）的 vec2 是否有交。

我们发现这个 vec1 和 vec2 在排序之后符合单调性，即你可以从其末尾开始访问，但有一个不符合条件的时候就 break。

这个做法的正确性显然， 实际上这个做法的均摊时间复杂度是 O(n \log n) 的，空间复杂度也一样，显然是可以通过的。

最后贴一下代码。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int tab[N << 2], len, n;
struct Square {
    int lx, ly, rx, ry;
    inline void read() {
        scanf("%d %d %d %d", &lx, &rx, &ly, &ry), ++lx, ++ly;
        tab[++len] = lx, tab[++len] = rx;
    }
    inline void print() { printf("%d %d %d %d\n", tab[lx] - 1, tab[rx], ly - 1, ry); }
    inline bool operator<(const Square &b) const { return ry < b.ry; }
    inline Square operator+(const Square &b) const { return {min(lx, b.lx), min(ly, b.ly), max(rx, b.rx), max(ry, b.ry)}; }
} a[N];
bool vis[N];
inline bool calc(int x, int y) { return !((a[x].ly > a[y].ry) || (a[y].ly > a[x].ry)); }
struct SegmentTree {
    vector<int> vec[N << 2], vec2[N << 2];  // vec 染色到矩形所有包含的线段上，vec2染色到所有有交该矩形的线段上。
    void update(int u, int L, int R, int l, int r, int v) {
        if (L > r || R < l) return;
        vec2[u].push_back(v);
        if (L >= l && R <= r) {
            vec[u].push_back(v);
            return;
        }
        int M = L + R >> 1;
        update(u << 1, L, M, l, r, v), update(u << 1 | 1, M + 1, R, l, r, v);
    }
    bool merge(int u, int L, int R, int l, int r, int v) {
        if (L > r || R < l) return 0;
        bool flag = 0;
        for (int i = vec[u].size() - 1; ~i; i = vec[u].size() - 1) {
            if (vis[vec[u][i]]) {
                vec[u].pop_back();
                continue;
            }
            if (!calc(vec[u][i], v)) break;
            a[v] = a[v] + a[vec[u][i]], vis[vec[u][i]] = 1;
            vec[u].pop_back();
            flag = 1;
        }
        if (L >= l && R <= r) {
            for (int i = vec2[u].size() - 1; ~i; i = vec2[u].size() - 1) {
                if (vis[vec2[u][i]]) {
                    vec2[u].pop_back();
                    continue;
                }
                if (!calc(vec2[u][i], v)) break;
                a[v] = a[v] + a[vec2[u][i]], vis[vec2[u][i]] = 1;
                vec2[u].pop_back();
                flag = 1;
            }
            return flag;
        }
        int M = L + R >> 1;
        return flag | merge(u << 1, L, M, l, r, v) | merge(u << 1 | 1, M + 1, R, l, r, v);
    }
} seg;
inline bool cmp(Square a, Square b) { return a.lx != b.lx ? a.lx < b.lx : (a.rx != b.rx ? a.rx < b.rx : (a.ly != b.ly ? a.ly < b.ly : a.ry < b.ry)); }
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) a[i].read();
    sort(a + 1, a + n + 1), sort(tab + 1, tab + len + 1), len = unique(tab + 1, tab + len + 1) - tab - 1;
    for (int i = 1; i <= n; i++) {
        a[i].lx = lower_bound(tab + 1, tab + len + 1, a[i].lx) - tab;
        a[i].rx = lower_bound(tab + 1, tab + len + 1, a[i].rx) - tab;
    }
    for (int i = 1; i <= n; i++) {
        while (seg.merge(1, 1, len, a[i].lx, a[i].rx, i))
            ;
        seg.update(1, 1, len, a[i].lx, a[i].rx, i);
    }
    // for (int i = 1; i <= n; i++) --a[i].lx, --a[i].ly;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) a[++cnt] = a[i];
    sort(a + 1, a + cnt + 1, cmp), cout << cnt << endl;
    for (int i = 1; i <= cnt; i++) a[i].print();
    return 0;
}