CF1401E Divide Square 题解

题意：

给定一个 \(10^6\times10^6\) 的正方形，\(n\) 条横线和 \(m\) 条竖线穿过了它，求这些线把正方形分成了多少个部分。

保证不存在两条线段在同一条线上，并且每个线段至少与正方形的一条边相交。

输入格式：

第一行包含两个整数 \(n\) 和 \(m\) ( \(0 \leq n, m \leq 10^5\) ) —— 水平线段和垂直线段的数量。

接下来的 \(n\) 行包含水平线段的描述。第 \(i\) 行包含三个整数 \(y_i\)、\(lx_i\) 和 \(rx_i\) \((0 < y_i < 10^6,~0 \leq lx_i < rx_i \leq 10^6)\)，表示该线段连接 \((lx_i, y_i)\) 和 \((rx_i, y_i)\)。

接下来的 \(m\) 行包含垂直线段的描述。第 \(i\) 行包含三个整数 \(x_i\)、\(ly_i\) 和 \(ry_i\) \((0 < x_i < 10^6,~0 \leq ly_i < ry_i \leq 10^6)\)，表示该线段连接 \((x_i, ly_i)\) 和 \((x_i, ry_i)\)。

输出格式：

打印在绘制所有线段后正方形被分割成的部分数量。

tips：

The sample is like this:

二维偏序问题的通常解法是枚举一维、维护一维

在本题中并不能直接套用这种方法，但是基本上还是这个思路。

首先有一个结论，对于一条竖线，它与其他线段的交点总数为它的贡献。

除了一种特殊的情况，就是任何将大正方形直接切成两半的线段，会多生成一个部分。

这里说的任何是指，如果我们只计算竖边产生的贡献，那么特殊的横边会产生 \(1\) 的贡献（其他则不会）

如果我们对横边进行某种维护，然后枚举竖边，查询每个竖边能对答案造成多少贡献。

考虑把横坐标看作时间 \(t\) ，维护每个纵坐标 \(i\) 在当前时刻是否被线段覆盖。

如果将横边视作修改操作，竖边视作查询操作，则可以用「单点修改 + 区间查询」树状数组维护。

我们把修改和询问分别按时间排序，如果当前时刻同时有修改和查询，就先修改后查询。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
int lowbit(int x) { return x & (-x); }
#define N ((int)(1e5 + 15))
#define M ((int)(1e6 + 15))

int n, m, res = 1, tot1, tot2;
int tr[M], y[N], x[N], lx[N], rx[N], ly[N], ry[N];
struct node1 { int t, p, v; } q1[N * 2];
struct node2 { int t, l ,r; } q2[N * 2];
bool operator<(node1 a, node1 b) { return a.t < b.t; }
bool operator<(node2 a, node2 b) { return a.t < b.t; }
void add(node1 now) { for(int i = now.p; i <= 1e6; i += lowbit(i)) tr[i] += now.v; }
int sum(int x, int r = 0) { for(int i = x; i; i -= lowbit(i)) r += tr[i]; return r; }
int qry(node2 now) { return sum(now.r) - sum(now.l - 1); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> y[i] >> lx[i] >> rx[i];
        if(lx[i] == 0 && rx[i] == 1e6) ++res;
        ++y[i]; ++lx[i]; ++rx[i];
        q1[++tot1] = {lx[i] - 1, y[i], 1};
        q1[++tot1] = {rx[i], y[i], -1};
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> x[i] >> ly[i] >> ry[i];
        if(ly[i] == 0 && ry[i] == 1e6) ++res;
        ++x[i]; ++ly[i]; ++ry[i];
        q2[++tot2] = {x[i], ly[i], ry[i]};
    }
    sort(q1 + 1, q1 + 1 + tot1); sort(q2 + 1, q2 + 1 + tot2);
    int cnt1 = 1, cnt2 = 1;
    for(; cnt1 <= tot1 && q1[cnt1].t == 0; ++cnt1) add(q1[cnt1]);
    for(int t = 1; t <= 1e6; t++)
    {
        for(; cnt2 <= tot2 && q2[cnt2].t == t; ++cnt2) res += qry(q2[cnt2]);
        for(; cnt1 <= tot1 && q1[cnt1].t == t; ++cnt1) add(q1[cnt1]);
    }
    cout << res << '\n';
    return 0;
}