样例没过,求调
查看原帖
样例没过,求调
941502
_Gabriel_楼主2024/8/18 22:37
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
struct node {
    ll x, y_high, y_low, flag;
}E[N * 2];
ll rk[N * 2], val[N];
ll ans;
int n, len, cnt = 1, max_y;

struct edge {
	ll l, r, len, cnt, flag;    
}tree[N * 8];

void pushup(int id) {
    if (tree[id].l == max_y && tree[id].r == max_y) {
        return;
    }
    if (tree[id].flag) {
        tree[id].len = val[tree[id].r + 1] - val[tree[id].l];
    } else {
		tree[id].len = tree[id << 1].len + tree[id << 1 | 1].len;
    }
}

void build(int id, int l, int r) {
    tree[id].l = l;
    tree[id].r = r;
    tree[id].flag = tree[id].len = 0;
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
	build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);
}

void update(int id, int l, int r, int val) {
    if (l <= tree[id].l && tree[id].r <= r) {
        tree[id].flag += val;
        pushup(id);
        return;
    }
    int mid = (tree[id].l + tree[id].r) >> 1;
	if (l <= mid) {
        update(id << 1, l, mid, val);
    }    
    if (r > mid) {
        update(id << 1 | 1, mid + 1, r, val);
    }
    pushup(id);
}

bool cmp(const node& x, const node& y) {
    if (x.x != y.x) {
        return x.x < y.x;
    } else {
        return x.flag > y.flag;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        ll xa, ya, xb, yb;
        scanf("%lld%lld%lld%lld", &xa, &ya, &xb, &yb);
        E[cnt].x = xa;
        E[cnt].y_high = yb;
        E[cnt].y_low = ya;
        E[cnt].flag = 1;
        rk[cnt++] = ya;
        E[cnt].x = xb;
        E[cnt].y_high = yb;
        E[cnt].y_low = ya;
        E[cnt].flag = -1;
        rk[cnt++] = yb;        
    }
    sort(rk + 1, rk + cnt + 1);
    len = unique(rk + 1, rk + cnt + 1) - rk - 1;
    for (int i = 1; i <= cnt; i++) {
        int pos1 = lower_bound(rk + 1, rk + len + 1, E[i].y_high) - rk - 1;
        int pos2 = lower_bound(rk + 1, rk + len + 1, E[i].y_low) - rk - 1;
        val[pos1] = E[i].y_high;
        val[pos2] = E[i].y_low;
        E[i].y_high = pos1;
        E[i].y_low = pos2;
        max_y = max(max_y, pos1);
    }
    sort(E + 1, E + cnt + 1, cmp);
    build(1, 1, cnt);
    for (int i = 1; i < cnt; i++) {
        update(1, E[i].y_low, E[i].y_high - 1, E[i].flag);
        ans += tree[1].len * (E[i + 1].x - E[i].x);
    }
    printf("%lld", ans);
    return 0;
}
2024/8/18 22:37
加载中...