一、题意理解

1. 操作类型

有三种操作：

• I x1 y1 x2 y2：新增一个领主，要占领矩形 $(x_1,y_1)-(x_2,y_2)$
• D x：删除第 $x$ 个新增的领主（按 I 的顺序编号）
• Q x1 y1 x2 y2：查询矩形 $(x_1,y_1)-(x_2,y_2)$ 与当前存在的所有领主矩形相交的数量

相交定义：两个矩形有公共点（即边界相接也算相交）。

---

二、核心问题

我们要支持动态插入、删除矩形，以及查询与给定矩形相交的矩形数量。

这是一个二维平面上的矩形相交计数问题，且支持删除操作。

---

三、问题转化

1. 矩形相交条件

两个矩形 $A=[x_1,x_2]\times[y_1,y_2]$ 和 $B=[x'_1,x'_2]\times[y'_1,y'_2]$ 相交的充要条件是：

$$x_1 \le x'_2 \quad\&\quad x'_1 \le x_2 \quad\&\quad y_1 \le y'_2 \quad\&\quad y'_1 \le y_2 $$

换句话说，在 $x$ 轴和 $y$ 轴上的投影区间都要相交。

---

四、标准解法思路（容斥）

对于查询矩形 $Q$，要统计与它相交的矩形数量 $N$。

设总矩形数为 $M$，则 $N = M -$（与 $Q$ 不相交的矩形数）。

与 $Q$ 不相交的情况有四种：

1. 矩形在 $Q$ 的左边：$x'_2 < x_1$
2. 矩形在 $Q$ 的右边：$x'_1 > x_2$
3. 矩形在 $Q$ 的下边：$y'_2 < y_1$
4. 矩形在 $Q$ 的上边：$y'_1 > y_2$

但这些情况可能有重叠（矩形同时在左边和上边等），需要容斥。

但更常见的方法是：直接计算相交数 = 总数 - 全不相交数，全不相交的矩形满足：

$$x'_2 < x_1 \quad\text{或}\quad x'_1 > x_2 \quad\text{或}\quad y'_2 < y_1 \quad\text{或}\quad y'_1 > y_2 $$

用容斥原理可以转化为计算一些偏序关系的数量。

---

五、代码中的巧妙做法

这个代码采用了一种更直接的方法：将相交条件转化为四维偏序问题。

设领主矩形为 $R=(x_1,x_2,y_1,y_2)$，查询矩形为 $Q=(X_1,X_2,Y_1,Y_2)$。

相交的条件 $x_1 \le X_2$ 且 $X_1 \le x_2$ 且 $y_1 \le Y_2$ 且 $Y_1 \le y_2$ 可以拆成 4 个不等式，每个不等式对应一个维度的比较。

我们可以统计不满足某个不等式的矩形数，然后容斥。但直接容斥 4 个条件很复杂。

代码实际采用了另一种思路：将每个矩形看作四维空间中的一个点 $(x_1,x_2,y_1,y_2)$，查询就是统计满足四维偏序关系的点数。

---

六、坐标离散化

由于坐标范围很大（无限平面），我们需要离散化：

for (int j = 1; j <= n; ++j) aux[j] = a[0][j];
for (int j = 1; j <= n; ++j) aux[j + n] = a[2][j];
sort(aux + 1, aux + 2 * n + 1);
int cntf = unique(aux + 1, aux + 2 * n + 1) - aux - 1;
for (int j = 1; j <= n; ++j) {
    a[0][j] = lower_bound(aux + 1, aux + cntf + 1, a[0][j]) - aux;
}
for (int j = 1; j <= n; ++j) {
    a[2][j] = lower_bound(aux + 1, aux + cntf + 1, a[2][j]) - aux;
}

对 $x_1,x_2,y_1,y_2$ 分别离散化，坐标值变为 $1$ 到 $2n$ 的整数。

---

七、分步统计

代码将相交矩形数 $N$ 分解为：

$$N = \text{总数} - (\text{在左边的矩形} + \text{在右边的矩形} + \text{在下边的矩形} + \text{在上边的矩形}) + \text{重复扣除的} $$

但实际上代码的做法是：

1. 先假设所有矩形都与查询相交，即 ans[i] = cnt_ins - cnt_del（当前存在的矩形总数）。
2. 然后减去那些一定不相交的矩形数。

一定不相交的四种情况：

• 在左边：$x_2 < X_1$
• 在右边：$x_1 > X_2$
• 在下边：$y_2 < Y_1$
• 在上边：$y_1 > Y_2$

7.1 第一轮统计

if (op[i] == 0) { // 查询
    ans[i] += sum1[0] - query1<0>(a[2][i]);  // 在左边：x2 < X1
    ans[i] += sum1[1] - query1<1>(a[3][i]);  // 在下边：y2 < Y1
    ans[i] += query1<2>(a[0][i] - 1);        // 在右边：x1 > X2
    ans[i] += query1<3>(a[1][i] - 1);        // 在上边：y1 > Y2
}

这里 bit1[0] 存储所有领主矩形的 $x_2$ 值，sum1[0] 是总数，sum1[0] - query1(a[2][i]) 统计 $x_2 < X_1$ 的矩形数（因为 $a[2][i]$ 是查询的 $X_1$）。

其他三个同理。

但这还不够，因为这样会重复扣除那些同时满足两个条件的矩形（如在左边且在下边），所以还需要加回这些重复的部分。

---

7.2 第二轮统计（处理重复扣除）

代码用四个树状数组 bit1[0..3] 分别维护 $x_2, y_2, x_1, y_1$ 的分布，但只是单维统计，无法处理两维组合的情况。

为了解决二维组合（如左边且上边），代码采用了四维偏序的容斥：

对于查询 $Q=(X_1,X_2,Y_1,Y_2)$，领主矩形 $R=(x_1,x_2,y_1,y_2)$。

考虑 $R$ 在 $Q$ 的左上方的情况：

• 在左边：$x_2 < X_1$
• 在上边：$y_1 > Y_2$

这两个条件组合。

代码用四个向量数组 vec1, vec2, vec3, vec4 来记录需要处理的二维查询和更新。

---

八、二维树状数组的替代方案

由于需要支持删除，且 $n \le 10^5$，直接二维树状数组或线段树内存太大。

代码采用了分治树状数组的技巧：

• 将二维条件 $(x_2 < X_1, y_1 > Y_2)$ 转化为：在 $x_2$ 维度上树状数组，每个节点维护一个 $y_1$ 的树状数组。
• 但这样空间 $O(n \log^2 n)$ 还是大。

所以代码实际上用了离线处理 + 按第一维排序的方法。

对于每个查询 $Q$，要统计 $x_2 < X_1$ 且 $y_1 > Y_2$ 的矩形数。

我们可以按 $x_2$ 从小到大处理，维护当前 $x_2 < \text{当前值}$ 的所有矩形的 $y_1$ 分布（用树状数组）。

具体做法：

1. 将所有领主矩形的 $(x_2, y_1)$ 和查询的 $(X_1, Y_2)$ 放在一起。
2. 按第一维排序。
3. 遇到领主矩形：在 $y_1$ 树状数组中 +1。
4. 遇到查询：查询 $y_1 > Y_2$ 的数量。

但这需要处理动态插入和删除。代码中，领主矩形的插入和删除也看作“事件”，按 $x_2$ 排序后一起处理。

---

九、代码结构解析

9.1 预处理

for (int i = 1; i <= n; ++i) {
    if (op[i]) { // 插入或删除
        // 在 vec1, vec2, vec3, vec4 中记录事件
        // 例如 vec1[x].emplace_back(v, op[i]) 表示在 x 处有事件
    } else { // 查询
        // 在 vec1, vec2, vec3, vec4 中记录查询
        // 例如 vec1[x].emplace_back(v, i+1) 表示查询
    }
}

这里 vec1[x] 对应 $x_2$ 维度，vec3[x] 对应 $n*2 - x_1$（处理右边条件）。

9.2 处理二维条件

for (int i = 1; i <= n * 2; ++i) {
    for (auto [u, v] : vec1[i]) {
        if (v > 1) { // 查询
            ans[v - 1] += query2<0>(u);
        } else { // 更新
            add2<0>(u, v);
            tmp0.push_back(u);
        }
    }
    // ... 类似处理 vec2, vec3, vec4
    // 清空树状数组
}

这里 query2<0>(u) 查询 $y_1 > u$ 的数量（对应 $y_1 > Y_2$）。

通过这种方式，我们处理了四种二维组合：

• $x_2 < X_1$ 且 $y_1 > Y_2$
• $x_2 < X_1$ 且 $y_2 < Y_1$
• $x_1 > X_2$ 且 $y_1 > Y_2$
• $x_1 > X_2$ 且 $y_2 < Y_1$

这四种情况在第一轮统计中被重复扣除了，现在加回来。

---

十、算法总结

1. 离散化坐标到 $[1, 2n]$。
2. 第一轮统计：用四个一维树状数组分别统计四种不相交情况（左、右、下、上）。
3. 第二轮统计：离线处理四种二维组合条件（左上、左下、右上、右下），用一维树状数组按第一维排序后处理第二维。
4. 容斥原理：最终相交数 = 总数 - 单边不相交数 + 双边组合数（因为单边统计时，双边情况被扣了两次，需要加回一次）。

时间复杂度：$O(n \log^2 n)$，由于常数小，可以通过 $n=10^5$。

空间复杂度：$O(n \log n)$。

---

十一、样例验证

样例：

5
I 1 1 3 3
Q 2 2 4 4
I 1 1 5 5
D 1
Q 2 3 3 3

• 第一个查询时，只有矩形 (1,1)-(3,3)，与查询矩形 (2,2)-(4,4) 相交，输出 1。
• 删除第一个矩形后，剩下矩形 (1,1)-(5,5)，与查询 (2,3)-(3,3) 相交，输出 1。

算法正确。

---

这个解法是经典的四维偏序容斥 + 离线树状数组分治，巧妙地将二维矩形相交计数转化为多个低维偏序问题，适合处理 $10^5$ 级别的动态问题。