NOIP2018提高组模拟赛8.25-矩阵交集问题

题目描述：

给定多个矩形，每个矩形由其左下角和右上角的坐标定义。任务是找到这些矩形的交集的最大面积。

输入格式：

第一行包含一个整数 T，表示测试数据的组数。对于每组测试数据，第一行包含两个整数 n 和 m，分别表示矩形的数量和允许的最大删除数量。接下来 n 行，每行包含两个整数 x 和 y，表示矩形的宽度和高度。

输出格式：

对于每组测试数据，输出一行，包含一个整数，表示所有矩形交集的最大面积。

数据范围：

1 ≤ T ≤ 10，1 ≤ n ≤ 10^5，1 ≤ m ≤ n，1 ≤ x, y ≤ 10^5。

分析：

所有矩形的交集最大面积可以通过计算所有矩形宽度和高度的最小值来确定，即 min(x) * min(y)。为了高效地解决这个问题，我们首先按照矩形的宽度进行排序，然后使用一个权值线段树来维护高度信息。具体步骤如下：

1. 对所有矩形按宽度从小到大排序。
2. 遍历排序后的矩形，使用权值线段树记录每个矩形的高度。
3. 在遍历过程中，动态维护当前剩余矩形的高度最小值，并计算当前矩形的宽度与高度最小值的乘积，更新答案。

代码实现：

#include 
#include 
#define LL long long
const int maxn = 1e5 + 7;
const int maxp = 1e5;
using namespace std;

int test, n, m;
int t[maxn * 4];
LL ans;

struct Node {
    int x, y;
} a[maxn];

bool cmp(Node x, Node y) {
    return x.x }

void update(int p, int l, int r, int x, int k) {
    if (l == r) {
        t[p] += k;
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid) update(p * 2, l, mid, x, k);
    else update(p * 2 + 1, mid + 1, r, x, k);
    t[p] = t[p * 2] + t[p * 2 + 1];
}

int getRank(int p, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) / 2;
    if (k <= t[p * 2]) return getRank(p * 2, l, mid, k);
    else return getRank(p * 2 + 1, mid + 1, r, k - t[p * 2]);
}

int main() {
    freopen("d.in", "r", stdin);
    freopen("d.out", "w", stdout);
    scanf("%d", &test);
    while (test--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &a[i].x, &a[i].y);
        }
        sort(a + 1, a + n + 1, cmp);
        ans = 0;
        for (int i = n; i > 0; i--) {
            update(1, 1, maxp, a[i].y, 1);
            if (i - 1 > m) continue;
            int d = getRank(1, 1, maxp, m - (i - 1) + 1);
            ans = max(ans, (LL)a[i].x * (LL)d);
        }
        for (int i = 1; i <= n; i++) update(1, 1, maxp, a[i].y, -1);
        printf("%lld\n", ans);
    }
    return 0;
}