QRECT 题解

题目分析

本题要求处理三种操作：插入矩形、删除矩形、查询与给定矩形至少有一个公共点的矩形数量。坐标范围极大（1≤x1≤x2≤1e9，1≤y1≤y2≤1e9），且操作数量可达1e5，直接暴力查询会超时，需设计高效算法。

核心思路

1. 转化问题：利用补集与容斥原理

两矩形相交的反面是不相交。设当前存在的矩形总数为su，则相交数量 = su - 不相交数量。

两矩形A(x1,y1,x2,y2)与B(a1,b1,a2,b2)不相交的情况有4种：

• A在B左边：A.x2 < B.x1
• A在B右边：A.x1 > B.x2
• A在B下边：A.y2 < B.y1
• A在B上边：A.y1 > B.y2

设这4种情况的数量为左、右、下、上，则不相交数量需用容斥原理计算：

不相交数量 = 左 + 右 + 下 + 上 - (左且下 + 左且上 + 右且下 + 右且上)

（更高阶的交叉项概率极低，且计算复杂，实际可通过分治处理）

2. 离线处理与离散化

• 离线处理：先读入所有操作，统一处理（便于分治和容斥计算）。
• 离散化：坐标范围极大，将所有出现的x1、x2、y1、y2收集后排序去重，用排名代替原始坐标，压缩到可处理范围（便于用树状数组操作）。

3. CDQ分治与树状数组

• 树状数组（BIT）：高效维护动态集合的插入、删除和范围查询，用于统计满足特定条件的矩形数量。
• CDQ分治：按时间顺序分割操作序列，递归处理子区间，合并时统计跨区间的交叉项（如“左且下”），解决离线动态问题的时间顺序依赖。

算法步骤

1. 读入操作并预处理：

   • 记录所有插入（I）、删除（D）、查询（Q）操作的矩形信息。
   • 收集所有坐标，离散化x和y坐标。

2. 计算初始不相交数量：

   • 用树状数组统计“左+右”（x方向不相交）和“下+上”（y方向不相交），从总数su中减去，得到初步结果。

3. 分治处理交叉项：

   • 用CDQ分治统计“左且下、左且上、右且下、右且上”的数量，加回初步结果（修正容斥中的重复减去项）。

4. 输出查询结果：每个查询的最终结果为修正后的相交数量。

代码解析

数据结构

• struct Rec：存储插入的矩形坐标。
• struct node：存储操作的矩形信息及类型（插入0/删除-1/查询id）。
• Bit：树状数组，支持插入、删除（加减1）和范围查询。

关键函数

1. 离散化：

   • 收集所有x1、x2到数组a，y1、y2到数组b，排序去重后用lower_bound映射原始坐标到排名。

2. 初始不相交计算：

   • 对x方向：用树状数组统计“左”（x2 < qx1）和“右”（x1 > qx2）的数量，从ans中减去。
   • 对y方向：同理统计“下”和“上”的数量，从ans中减去。

3. CDQ分治（solve函数）：

   • 递归分割操作序列，合并时按x坐标排序，用树状数组统计y方向的交叉项（如“左且下”），将结果加回ans。

算法标签

• CDQ分治
• 容斥原理
• 离散化
• 树状数组（BIT）
• 离线处理

完整代码

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define fix(x) fixed<<setprecision(x)
#define pii pair<int,int>
#define vint vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
#define db double
#define ld long db
using namespace std;

int read() {
    int g = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || '9' < ch) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while ('0' <= ch && ch <= '9') {
        g = g * 10 + ch - '0';
        ch = getchar();
    }
    return g * f;
}

const int N = 1e5 + 5;
int maxn, n, a[N << 1], b[N << 1], xcnt, ycnt, cnt, su, qsu, ans[N];
char opt[10];

struct Rec { int x1, y1, x2, y2; } rec[N];
struct node { int x1, y1, x2, y2, id; } sol[N];

struct Bit {
    int t[N << 1];
    void clear() { memset(t, 0, sizeof(t)); }
    void insert(int x, int y) { for (; x <= maxn; x += x & -x) t[x] += y; }
    int query(int x) { int re = 0; for (; x; x -= x & -x) re += t[x]; return re; }
} L, R;

void solve(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);

    // 统计左且下 + 左且上
    sort(sol + l, sol + mid + 1, [](node a, node b) { return a.x2 < b.x2; });
    sort(sol + mid + 1, sol + r + 1, [](node a, node b) { return a.x1 < b.x1; });
    int nl = l;
    rep(i, mid + 1, r) {
        while (nl <= mid && sol[nl].x2 < sol[i].x1) {
            if (sol[nl].id == 0) L.insert(sol[nl].y1, 1), R.insert(sol[nl].y2, 1);
            if (sol[nl].id == -1) L.insert(sol[nl].y1, -1), R.insert(sol[nl].y2, -1);
            nl++;
        }
        if (sol[i].id > 0)
            ans[sol[i].id] += L.query(maxn) - L.query(sol[i].y2) + R.query(sol[i].y1 - 1);
    }
    rep(i, l, nl - 1) {
        if (sol[i].id == 0) L.insert(sol[i].y1, -1), R.insert(sol[i].y2, -1);
        if (sol[i].id == -1) L.insert(sol[i].y1, 1), R.insert(sol[i].y2, 1);
    }

    // 统计右且下 + 右且上
    sort(sol + l, sol + mid + 1, [](node a, node b) { return a.x1 > b.x1; });
    sort(sol + mid + 1, sol + r + 1, [](node a, node b) { return a.x2 > b.x2; });
    nl = l;
    rep(i, mid + 1, r) {
        while (nl <= mid && sol[nl].x1 > sol[i].x2) {
            if (sol[nl].id == 0) L.insert(sol[nl].y1, 1), R.insert(sol[nl].y2, 1);
            if (sol[nl].id == -1) L.insert(sol[nl].y1, -1), R.insert(sol[nl].y2, -1);
            nl++;
        }
        if (sol[i].id > 0)
            ans[sol[i].id] += L.query(maxn) - L.query(sol[i].y2) + R.query(sol[i].y1 - 1);
    }
    rep(i, l, nl - 1) {
        if (sol[i].id == 0) L.insert(sol[i].y1, -1), R.insert(sol[i].y2, -1);
        if (sol[i].id == -1) L.insert(sol[i].y1, 1), R.insert(sol[i].y2, 1);
    }
}

void get(int opt, int &x) {
    if (opt == 0) x = lower_bound(a + 1, a + xcnt + 1, x) - a;
    else x = lower_bound(b + 1, b + ycnt + 1, x) - b;
}

signed main() {
    n = read();
    rep(i, 1, n) {
        scanf("%s", opt);
        if (opt[0] == 'I') {
            cnt++, su++;
            int x1 = read(), y1 = read(), x2 = read(), y2 = read();
            rec[cnt] = {x1, y1, x2, y2};
            a[++xcnt] = x1, a[++xcnt] = x2;
            b[++ycnt] = y1, b[++ycnt] = y2;
            sol[i] = {x1, y1, x2, y2, 0};
        }
        if (opt[0] == 'D') {
            su--;
            int x = read();
            auto &r = rec[x];
            sol[i] = {r.x1, r.y1, r.x2, r.y2, -1};
        }
        if (opt[0] == 'Q') {
            qsu++;
            ans[qsu] = su;
            int x1 = read(), y1 = read(), x2 = read(), y2 = read();
            sol[i] = {x1, y1, x2, y2, qsu};
            a[++xcnt] = x1, a[++xcnt] = x2;
            b[++ycnt] = y1, b[++ycnt] = y2;
        }
    }

    // 离散化
    sort(a + 1, a + xcnt + 1);
    sort(b + 1, b + ycnt + 1);
    xcnt = unique(a + 1, a + xcnt + 1) - a - 1;
    ycnt = unique(b + 1, b + ycnt + 1) - b - 1;
    maxn = max(xcnt, ycnt);

    // 映射坐标
    rep(i, 1, n) {
        get(0, sol[i].x1), get(0, sol[i].x2);
        get(1, sol[i].y1), get(1, sol[i].y2);
    }

    // 减去 x方向不相交（左+右）
    rep(i, 1, n) {
        if (sol[i].id == 0) L.insert(sol[i].x1, 1), R.insert(sol[i].x2, 1);
        if (sol[i].id == -1) L.insert(sol[i].x1, -1), R.insert(sol[i].x2, -1);
        if (sol[i].id > 0)
            ans[sol[i].id] -= L.query(maxn) - L.query(sol[i].x2) + R.query(sol[i].x1 - 1);
    }
    L.clear(), R.clear();

    // 减去 y方向不相交（下+上）
    rep(i, 1, n) {
        if (sol[i].id == 0) L.insert(sol[i].y1, 1), R.insert(sol[i].y2, 1);
        if (sol[i].id == -1) L.insert(sol[i].y1, -1), R.insert(sol[i].y2, -1);
        if (sol[i].id > 0)
            ans[sol[i].id] -= L.query(maxn) - L.query(sol[i].y2) + R.query(sol[i].y1 - 1);
    }
    L.clear(), R.clear();

    // 分治统计交叉项，加回修正
    solve(1, n);

    // 输出结果
    rep(i, 1, qsu) cout << ans[i] << '\n';
    return 0;
}