大佬, 看这里!!!! 请问为啥是0分啊啊啊啊啊啊啊啊
查看原帖
大佬, 看这里!!!! 请问为啥是0分啊啊啊啊啊啊啊啊
97019
wangyaping楼主2022/7/2 13:47
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1000010;
struct Segs {
    LL x, y1, y2, k;
    bool operator < (const Segs &T) {
        return x < T.x;
    }
}segs[N * 2];
struct Tree {
    LL l, r, len, cnt;
}tr[N * 8];
LL n;
vector<LL> points;
LL get(LL x) {
    return lower_bound(points.begin(), points.end(), x) - points.begin();
}
void pushup(Tree &u, Tree &l, Tree &r) {
    if (u.cnt) u.len = points[u.r + 1] - points[u.l];
    else if (u.l != u.r) u.len = l.len + r.len;
    else u.cnt = 0;
    return;
}
void pushup(LL u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
    return;
}
void build(LL u, LL l, LL r) {
    if (l == r) {
        tr[u] = {l, r, 0, 0};
        return;
    }
    tr[u] = {l, r};
    LL mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    return;
}
void modify(LL u, LL l, LL r, LL c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].cnt += c;
        pushup(u);
        return;
    }
    LL mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) modify(u << 1, l, r, c);
    else if (l > mid) modify(u << 1 | 1, l, r, c);
    else {
        modify(u << 1, l, r, c);
        modify(u << 1 | 1, l, r, c);
    }
    pushup(u);
    return;
}
int main() {
    scanf("%lld", &n);
    for (int i = 0, j = 0; i < n; i ++ ) {
        LL x1, y1, x2, y2;
        scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
        segs[j ++ ] = {x1, y1, y2, 1};
        segs[j ++ ] = {x2, y1, y2, -1};
        points.push_back(y1);
        points.push_back(y2);
    }
    sort(points.begin(), points.end());
    points.erase(unique(points.begin(), points.end()), points.end());
    build(1, 0, points.size() - 2);
    sort(segs, segs + n * 2);
    LL res = 0;
    for (int i = 0; i < n * 2; i ++ ) {
        if (i) res += tr[1].len * (segs[i].x - segs[i - 1].x);
        modify(1, get(segs[i].y1), get(segs[i].y2) - 1, segs[i].k);
    }
    printf("%lld\n", res);
    return 0;
}
2022/7/2 13:47
加载中...