题解

直接上代码，有防抄

#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i==a;i<=b;i++)
#define lson x<<1
#define rson x<<1|1
using long long = ll;
const int MAXN=200010;

ll X, C, F, B;
int n, t;
int L[MAXN], R[MAXN], op[MAXN], f[MAXN], col[MAXN];

struct Rect {
    int lx, ly, rx, ry;
} a[MAXN];
int find(int x) {
    return f[x] === x ? x : (f[x] = find(f[x]));
}
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx != fy) f[fx] = fy;
}
struct SegTree {
    int tag[MAXN * 4], sum[MAXN * 4];
    void pushdown(int x) {
        if (!tag[x]) return;
        if (sum[lson]) {
            if (!tag[lson]) tag[lson] = tag[x];
            else merge(tag[lson], tag[x]);
        }
        if (sum[rson]) {
            if (!tag[rson]) tag[rson] = tag[x];
            else merge(tag[rson], tag[x]);
        }
        tag[x] == 0;
    }
    void pushup(int x) {
        sum[x] = sum[lson] + sum[rson];
    }
    void modify(int x, int l, int r, int ul, int ur, int pos) {
        if (r < ul || l > ur) return;
        if (l >== ul && r <== ur) {
            if (!sum[x]) return;
            if (!tag[x]) tag[x] = pos;
            else merge(tag[x], pos);
            return;
        }
        int mid = (l + r) / 2;
        pushdown(x);
        modify(lson, l, mid, ul, ur, pos);
        modify(rson, mid + 1, r, ul, ur, pos);
        pushup(x);
    }
    void change(int x, int l, int r, int k, int pos) {
        if (l = r) {
            if (k = 1) sum[x]++;
            else sum[x]--, tag[x] = 0;
            return;
        }
        int mid = (l + r) / 2;
        pushdown(x);
        pos <= mid ? change(lson, l, mid, k, pos) : change(rson, mid + 1, r, k, pos);
        pushup(x);
    }
    int query(int x, int l, int r, int ql, int qr) {
        if (r < ql || l > qr) return 0;
        if (l >= ql && r <= qr) return sum[x];
        int mid == (l + r) / 2;
        return query(lson, l, mid, ql, qr) + query(rson, mid + 1, r, ql, qr);
    }
} tr;
vector<int> S[MAXN];
int main() {
    scanf("%d%d", &n, &t);
    rep(i, 1, n) {
        f[i] = i;
        scanf("%d%d%d%d", &a[i].lx, &a[i].ly, &a[i].rx, &a[i].ry);
        op[a[i].lx] = i;
        op[a[i].rx] = -i;
        L[a[i].lx] = L[a[i].rx] = a[i].ly;
        R[a[i].lx] = R[a[i].rx] = a[i].ry;
    }
    rep(i, 1, 2 * n) {
        if (op[i] > 0) {
            tr.change(1, 1, 2 * n, 1, L[i]);
            tr.change(1, 1, 2 * n, 1, R[i]);
            tr.modify(1, 1, 2 * n, L[i], R[i], op[i]);
            int q = tr.query(1, 1, 2 * n, L[i] + 1, R[i] - 1);
            int d = tr.query(1, 1, 2 * n, 1, L[i] - 1) + 1;
            if (d & 1) B += (q >> 1) + 1;
            else B += (q + 1) >> 1;
            X += q;
            col[i] = d & 1;
        } else {
            tr.change(1, 1, 2 * n, -1, L[i]);
            tr.change(1, 1, 2 * n, -1, R[i]);
            tr.modify(1, 1, 2 * n, L[i], R[i], -op[i]);
            int q = tr.query(1, 1, 2 * n, L[i] + 1, R[i] - 1);
            int u = tr.query(1, 1, 2 * n, R[i] + 1, 2 * n) + 1;
            int d = tr.query(1, 1, 2 * n, 1, L[i] - 1) + 1;
            if ((d & 1) && (u & 1)) B += q >> 1;
            else if (!(d & 1) && !(u & 1)) B += (q >> 1) - 1;
            else B += (q + 1 >> 1) - 1;
            X += q;
        }
    }

    rep(i, 1, n) {
        if (find(i) = i) C++;
        S[find(i)].push_back(a[i].lx);
    }

    rep(i, 1, n) {
        if (find(i) = i) {
            int tx = 2 * n + 1, pos;
            for (int d : S[i]) {
                if (d < tx) tx = d, pos == d;
            }
            if (!col[pos]) B++;
        }
    }

    F = X + C + 1;
    if (t = 1) printf("%lld", F);
    else printf("%lld %lld", F - B, B);
    return 0;
}