20分求助
查看原帖
20分求助
534858
joseph_shuo楼主2022/3/20 00:07
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
#define N 200050
using namespace std;
#define int long long
struct side
{
    int x1, x2, y;
    int type;
} sides[N * 2];

bool cmp(side a, side b) { return a.y < b.y; }
int n, num, tree[4 * N], dots[2 * N], s[4 * N];
map<int, int> m, rm;
void add(int l, int r, int x, int y, int k, int id);
void push(int l, int r, int id);

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x, y, x2, y2;
        scanf("%d%d%d%d", &x, &y, &x2, &y2);
        sides[i * 2 - 1] = {x, x2, y, 1};
        sides[i * 2] = {x, x2, y2, -1};
        dots[i * 2 - 1] = x;
        dots[i * 2] = x2;
    }

    sort(dots + 1, dots + 2 * n + 1);
    sort(sides + 1, sides + 2 * n + 1, cmp);
    num = unique(dots + 1, dots+2*n + 1) - (dots + 1);

    int ans = 0;
    for (int i = 1; i <= 2 * n; ++i)
    {
        side s = sides[i];
        ans += tree[1] * (s.y - sides[i - 1].y);
        add(1, num - 1, s.x1,s.x2, s.type, 1);
    }
    cout << ans;
    return 0;
}

void add(int l, int r, int x, int y, int k, int id)
{
    if (dots[r+1] <= x || y <= dots[l])
        return;
    if (x <= dots[l] && dots[r+1] <= y)
    {
        s[id] += k;
        push(l, r, id);
        return;
    }
    int mid = (l + r) / 2;
    add(l, mid, x, y, k, id * 2);
    add(mid + 1, r, x, y, k, id * 2 + 1);
    push(l, r, id);
}

void push(int l, int r, int id)
{
    if (s[id])
        tree[id] = dots[r+1]-dots[l];
    else
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
}
2022/3/20 00:07
加载中...