解题

ai写的

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

// 重写宏定义，替换原名，循环写法微调
#define For(i, st, ed) for(int i = st; i <= ed; ++i)
#define ls p << 1
#define rs p << 1 | 1
typedef long long ll;

// 常量改名
const int LIM = 200010;

// 全局变量全部重命名
ll totalCross, blockCnt, ansF, blackNum;
int rectNum, taskType;
int lowY[LIM], highY[LIM], tagOp[LIM], fa[LIM], colorMark[LIM];

// 结构体字段重命名
struct Square {
    int x1, y1, x2, y2;
} rect[LIM];

// 并查集函数改名、内部写法微调
int getRoot(int u) {
    if(fa[u] != u) fa[u] = getRoot(fa[u]);
    return fa[u];
}
void unite(int u, int v) {
    int ru = getRoot(u), rv = getRoot(v);
    if(ru != rv) fa[ru] = rv;
}

// 线段树结构体改名，数组变量重命名
struct TreeSeg {
    int lazy[LIM * 4], cntNode[LIM * 4];

    void spread(int p) {
        if(!lazy[p]) return;
        if(cntNode[ls]) {
            if(!lazy[ls]) lazy[ls] = lazy[p];
            else unite(lazy[ls], lazy[p]);
        }
        if(cntNode[rs]) {
            if(!lazy[rs]) lazy[rs] = lazy[p];
            else unite(lazy[rs], lazy[p]);
        }
        lazy[p] = 0;
    }
    void upData(int p) {
        cntNode[p] = cntNode[ls] + cntNode[rs];
    }
    void rangeMark(int p, int l, int r, int L, int R, int id) {
        if(r < L || l > R) return;
        if(L <= l && r <= R) {
            if(!cntNode[p]) return;
            if(!lazy[p]) lazy[p] = id;
            else unite(lazy[p], id);
            return;
        }
        int mid = (l + r) / 2;
        spread(p);
        rangeMark(ls, l, mid, L, R, id);
        rangeMark(rs, mid+1, r, L, R, id);
        upData(p);
    }
    void pointUpdate(int p, int l, int r, int val, int pos) {
        if(l == r) {
            if(val == 1) cntNode[p]++;
            else {
                cntNode[p]--;
                lazy[p] = 0;
            }
            return;
        }
        int mid = (l + r) / 2;
        spread(p);
        if(pos <= mid) pointUpdate(ls, l, mid, val, pos);
        else pointUpdate(rs, mid+1, r, val, pos);
        upData(p);
    }
    int getSum(int p, int l, int r, int L, int R) {
        if(r < L || l > R) return 0;
        if(L <= l && r <= R) return cntNode[p];
        int mid = (l + r) / 2;
        return getSum(ls, l, mid, L, R) + getSum(rs, mid+1, r, L, R);
    }
} segTr;

vector<int> groupList[LIM];

int main() {
    scanf("%d%d", &rectNum, &taskType);
    For(i, 1, rectNum) {
        fa[i] = i;
        scanf("%d%d%d%d", &rect[i].x1, &rect[i].y1, &rect[i].x2, &rect[i].y2);
        tagOp[rect[i].x1] = i;
        tagOp[rect[i].x2] = -i;
        lowY[rect[i].x1] = lowY[rect[i].x2] = rect[i].y1;
        highY[rect[i].x1] = highY[rect[i].x2] = rect[i].y2;
    }

    For(pos, 1, rectNum * 2) {
        int cur = tagOp[pos];
        if(cur > 0) {
            segTr.pointUpdate(1, 1, rectNum*2, 1, lowY[pos]);
            segTr.pointUpdate(1, 1, rectNum*2, 1, highY[pos]);
            segTr.rangeMark(1, 1, rectNum*2, lowY[pos], highY[pos], cur);

            int midSum = segTr.getSum(1, 1, rectNum*2, lowY[pos]+1, highY[pos]-1);
            int leftCnt = segTr.getSum(1, 1, rectNum*2, 1, lowY[pos]-1) + 1;

            if(leftCnt & 1) blackNum += (midSum >> 1) + 1;
            else blackNum += (midSum + 1) >> 1;
            totalCross += midSum;
            colorMark[pos] = leftCnt & 1;
        } else {
            int id = -cur;
            segTr.pointUpdate(1, 1, rectNum*2, -1, lowY[pos]);
            segTr.pointUpdate(1, 1, rectNum*2, -1, highY[pos]);
            segTr.rangeMark(1, 1, rectNum*2, lowY[pos], highY[pos], id);

            int midSum = segTr.getSum(1, 1, rectNum*2, lowY[pos]+1, highY[pos]-1);
            int rightCnt = segTr.getSum(1, 1, rectNum*2, highY[pos]+1, rectNum*2) + 1;
            int leftCnt = segTr.getSum(1, 1, rectNum*2, 1, lowY[pos]-1) + 1;

            bool lOdd = leftCnt & 1;
            bool rOdd = rightCnt & 1;
            if(lOdd && rOdd) blackNum += midSum / 2;
            else if(!lOdd && !rOdd) blackNum += (midSum / 2) - 1;
            else blackNum += ((midSum + 1) >> 1) - 1;
            totalCross += midSum;
        }
    }

    // 统计连通块
    For(i, 1, rectNum) {
        int rt = getRoot(i);
        if(rt == i) blockCnt++;
        groupList[rt].push_back(rect[i].x1);
    }

    // 统计黑色修正
    For(i, 1, rectNum) {
        if(getRoot(i) == i) {
            int minX = rectNum * 2 + 1;
            int pst = 0;
            for(int val : groupList[i]) {
                if(val < minX) {
                    minX = val;
                    pst = val;
                }
            }
            if(!colorMark[pst]) blackNum++;
        }
    }

    ansF = totalCross + blockCnt + 1;
    if(taskType == 1) {
        printf("%lld\n", ansF);
    } else {
        printf("%lld %lld\n", ansF - blackNum, blackNum);
    }
    return 0;
}