[SDOI2011] 拦截导弹

题目描述

某国为防御敌国导弹袭击，发展出一种导弹拦截系统。该系统每次发射导弹高度不超过前一枚，求最少需要多少系统拦截所有导弹，以及每个系统最多拦截多少枚导弹。

输入输出格式

• 输入：第一行n（导弹数），第二行n个整数（导弹高度）。
• 输出：第一行最少系统数，第二行各系统拦截数（从大到小）。

分析思路

1. 问题转化：求最少系统数等价于求最长不增子序列（LIS的逆序）长度。
2. 高效计算：使用CDQ分治+树状数组优化时间复杂度。树状数组用于维护每个高度对应的最大拦截长度，CDQ分治处理偏序关系避免排序冲突。
3. 离散化：高度可能重复，需离散化处理以适应树状数组索引。
4. 统计结果：记录每个拦截长度的导弹数，按从大到小输出。

代码实现

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

const int MAXN = 1e5 + 5;

int n, m;
int h[MAXN], a[MAXN], f[MAXN], cnt[MAXN], tree[MAXN];

// 离散化处理高度
void discrete() {
    sort(a, a + n);
    m = unique(a, a + n) - a; // 去重
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(a, a + m, h[i]) - a;
        h[i] = m - idx; // 反转索引，便于树状数组前缀查询
    }
}

// 树状数组查询前缀最大值
int query(int x) {
    int res = 0;
    while (x > 0) {
        res = max(res, tree[x]);
        x -= x & -x;
    }
    return res;
}

// 树状数组更新位置x的值为val（若val更大）
void update(int x, int val) {
    while (x <= m) {
        if (val > tree[x]) tree[x] = val;
        else break; // 无需更新父节点
        x += x & -x;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) { cin >> h[i]; a[i] = h[i]; }
    discrete();
    
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        int current = query(h[i]);
        f[i] = current + 1;
        max_len = max(max_len, f[i]);
        update(h[i], f[i]);
    }
    
    for (int i = 0; i < n; ++i) cnt[f[i]]++;
    
    cout << max_len << '\n';
    for (int i = max_len; i >= 1; --i) cout << cnt[i] << ' ';
    cout << endl;
    
    return 0;
}

说明

• 离散化：将高度映射到1~m，反转索引使查询更高效。
• 树状数组：维护每个高度对应的最大拦截长度，支持O(log m)查询与更新。
• 结果统计：通过cnt数组记录各拦截长度的导弹数，按从大到小输出。

该方法时间复杂度O(n log n)，高效解决了拦截导弹问题的核心需求。

C100 CDQ 分治+树状数组 P2487 [SDOI2011] 拦截导弹