题目描述

在二维平面上有一个无限的网格图形，初始状态下，所有的格子都是空白的。

现在有n个操作，每个操作是选择一行或一列，并在这行或这列上选择两个端点网格，把以这两个网格为端点的区间内的所有网格染黑（包含这两个端点）。

问经过n次操作以后，共有多少个格子被染黑，重复染色同一格子只计数一次。

样例

输入

3
1 2 3 2
2 5 2 3
1 4 3 4

输出

8

题解

似乎评论区都挂的是$O(n^2)$的代码。这题数据量是$1e4$，感觉会超。实际上拿$O(n^2)$跑下来是1447ms。
这里提供$O(nlogn)$的解法：离散化后先区间合并，之后把合并后的所有线段长累加进$ans$中。对于竖着的线段，在起点和终点分别打上tag。维护一个BIT，从下到上扫描，每次询问横着的区间内有多少根竖着的线段，和为交点个数。每次减掉即可。

AC代码

代码写得很丑。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
void compress(vector <int> &a)
{
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
int getIndex(vector <int> &a, int t)
{
    return lower_bound(a.begin(), a.end(), t) - a.begin() + 1;
}
struct seg
{
    int l, r, pos;
};
struct node
{
    int posX, posY, tag;
};
bool cmpSeg(seg a, seg b)
{
    if (a.pos == b.pos) return a.l < b.l;
    else return a.pos < b.pos;
}
bool cmpNode(node a, node b)
{
    if (a.posY == b.posY) return a.tag > b.tag;
    else return a.posY < b.posY;
}
void combine(vector <seg> &a, vector <seg> &cbna)
{
    int l = a[0].l, r = a[0].r, prevPos = a[0].pos;
    for (int i = 1; i < a.size(); ++i)
    {
        if (a[i].pos != prevPos)
        {
            cbna.push_back({l, r, prevPos});
            l = a[i].l, r = a[i].r, prevPos = a[i].pos;
        }
        else
        {
            if (a[i].l <= r) r = max(r, a[i].r);
            else
            {
                cbna.push_back({l, r, prevPos});
                l = a[i].l, r = a[i].r;
            }
        }
    }
    cbna.push_back({l, r, prevPos});
}
int BIT[MAXN] = {0};
void modify(int x, int c, int upper)
{
    while (x <= upper) BIT[x] += c, x += x & -x;
}
int query(int x)
{
    int s = 0;
    while (x > 0) s += BIT[x], x -= x & -x;
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    int n; cin >> n;
    vector <seg> segX, segY;
    vector <int> posX, posY;
    vector <node> tags;
    for (int i = 1; i <= n; ++i)
    {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) segY.push_back({min(y1, y2), max(y1, y2), x1});
        else segX.push_back({min(x1, x2), max(x1, x2), y1});
        posX.push_back(x1), posX.push_back(x2);
        posY.push_back(y1), posY.push_back(y2);
    }
    compress(posX), compress(posY);
    sort(segX.begin(), segX.end(), cmpSeg), sort(segY.begin(), segY.end(), cmpSeg);
    vector <seg> cbnSegX, cbnSegY;
    combine(segX, cbnSegX), combine(segY, cbnSegY);
    ll ans = 0;
    for (auto &i : cbnSegX) ans += i.r - i.l + 1;
    for (auto &i : cbnSegY)
    {
        ans += i.r - i.l + 1;
        tags.push_back({i.pos, i.l, 1}), tags.push_back({i.pos, i.r, -1});
    }
    sort(tags.begin(), tags.end(), cmpNode);
    int i = 0, j = 0;
    for (int p = 0; p < posY.size(); ++p)
    {
        while (j < tags.size() && tags[j].posY == posY[p] && tags[j].tag == 1)
            modify(getIndex(posX, tags[j].posX), 1, posX.size()), ++j;
        while (i < cbnSegX.size() && cbnSegX[i].pos == posY[p])
            ans -= query(getIndex(posX, cbnSegX[i].r)) - query(getIndex(posX, cbnSegX[i].l) - 1), ++i;
        while (j < tags.size() && tags[j].posY == posY[p] && tags[j].tag == -1)
            modify(getIndex(posX, tags[j].posX), -1, posX.size()), ++j;
    }
    cout << ans << endl;
    return 0;
}