矩形划分-几何

代码源OJ #853. 矩形划分；
参考题解；

普适的代价是抽象
Abstractness is the price of generality

显然，题目描述中过于抽象，出现理解困难的话可以参考题解视频；
我的理解（修正）如下：

1. 每次会给出两个点 p,q , 你需要在点 p,q 之间连一条线来划分矩形 , 保证 p,q 分别在矩形的一组对边上 , 即要么分别在左右边界上 , 要么分别在上下边界上。
2. 连的线并不要求是直线 , 可以是曲线 , 但不能与自己有交点 , 不能与矩形边界有除 p,q 以外的交点。
3. 一条线与其他每条线最多只有一个交点。
4. 每个交点只能为二线相交，不可以是更多线相交。
5. 保证给出的所有点两两不同。

思路

我们考虑构造过程：

1. 对于一个没有线的矩形，显然块数为1；
2. 每在矩形中添加一条与其他线没有交点的线，块数会增加1；
3. 每在矩形中添加一条与其他线有n个合法交点的线，块数会增加n+1；

所以我们可以发现，块数可以用：1+线数+交点数来表示；

对于交点数，我们可以发现所有纵向线都与每条横向线都一定有一个交点；
接下来我们讨论同方向线间的交点：
我们将线按一侧的坐标排序后，考虑另一侧的坐标，每出现一个逆序对，即说明出现了一次交错，即有一个交点；

具体操作可以使用归并排序统计逆序对；

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
pair<int, int> h[100005], w[100005], tmp[100005]; // line&clom
ll ds(pair<int, int> *a, int l, int r)
{
    // printf("%d %d\n", l, r);
    int mid = l + r >> 1;
    ll ans = 0;
    if (r - l + 1 > 2)
        ans = ds(a, l, mid) + ds(a, mid + 1, r);
    int i = l, j = mid + 1, c = 0;
    while (i <= mid && j <= r)
    {
        if (a[i].second <= a[j].second)
        {
            tmp[c++] = a[i];
            i++;
        }
        else
        {
            tmp[c++] = a[j];
            ans += mid - i + 1;
            j++;
        }
    }
    while (i <= mid)
    {
        tmp[c++] = a[i];
        i++;
    }
    while (j <= r)
    {
        tmp[c++] = a[j];
        j++;
    }
    for (int k = l; k <= r; k++)
    {
        a[k] = tmp[k - l];
    }
    return ans;
}
int main()
{
    int n, m, p, q;
    ll x, y;
    cin >> n >> m >> x >> y;
    for (int i = 1; i <= x; i++)
    {
        scanf("%d%d", &h[i].first, &h[i].second);
    }
    for (int i = 1; i <= y; i++)
    {
        scanf("%d%d", &w[i].first, &w[i].second);
    }
    sort(h + 1, h + 1 + (int)x);
    sort(w + 1, w + 1 + (int)y);
    ll ans = ds(h, 1, x) + ds(w, 1, y);
    cout << ans + x * y + x + y + 1;
    return 0;
}