2021 CSP-S2 题解（完整版）

[CSP-S 2021] 廊桥分配

一句话题意：

为国内航班和国际航分配廊桥的数量，使得最终停在廊桥的飞机总数最大。廊桥的使用原则是先到先得。

关键点：

1. 廊桥是先到先得，不是自由分配！
2. 所有的时间点是不同的（这是树状数组优化的前提）
3. 数据量$10^5$, 复杂度确定为$nlgn$级别，排序是必须的，则剩余的处理大致是一个O(n), 或加一个logn优化。

分析

1. 由于先到先得，所以按照区间起点排序。
2. 先不考虑廊桥的数量，单纯从为每个飞机分配廊桥的角度出发。通过随手画几个数据例子可以发现，当所有已经在使用的廊桥的结束时间都晚于当前飞机的到达时间时，必须为他单独分配一个新的廊桥。
3. 如果已经在使用的廊桥中，存在结束时间早于当前飞机到达时间，则可以利用这个旧廊桥。
4. 如果有多个旧廊桥可以利用，我们的选择是等价的。
5. 由此我们希望能利用旧廊桥的飞机，尽量利用最早分配的廊桥。

通过上面的分析和结论，我们发现，用这样的过程来模拟可以得到第一个廊桥最多的服务次数，前两个廊桥最多的服务次数，依次类推。我们得到了不同数量的廊桥能服务的最大飞机数。

然后就暴力枚举分配廊桥数量，取最大就可以了。

错误思路

1. 三分：两个增函数，$x_1+x_2=n$时，并不能唯一叠加出一个单峰函数，有可能是双峰函数，所以不行。

优化 - 树状数组（单点修改，前缀最值）

按照以上思路写代码，会出现一个不好解决的问题： 要在多个可用的旧廊桥中找编号最小的廊桥。使用暴力方法需要O(n) 的扫描，因此复杂度退化为$O(n^2)$。

这个操作很容易被抽象出来：在所有小于某个时间的编号中取最小值， 这明显是一个类似二维偏序的问题，所以使用树状数组来维护每个时间点对应的廊桥编号，动态取前缀最小值即可。

同是为了防止炸空间我还加了离散化。

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

typedef long long ll;


template<class T> bool chmax(T &a, const T &b) {
    if (a<b) {
    a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) {
    if (a>b) {
    a=b; return 1; } return 0; }

const int MOD     = 1e9+7;
const int INF     = 0x3f3f3f3f;
const ll  LLINF   = 0x3f3f3f3f3f3f3f3f;
const int MAXN    = 500005;
const int MAXM    = 2000005;

ll vis[MAXN], tim[MAXN];
int n, m1, m2;

struct BIT {
   
    int C[MAXN];
    int N;

    inline int lowbit(int x) {
    return x & (-x); }

    void init(int _N) {
   
        N = _N;
        memset(C, 0x3f, sizeof(C));
    }

    int getMin(int x) {
   
        int ret = INF;
        while(x > 0) {
   
            ret = min(ret, C[x]);
            x -= lowbit(x);
        }
        return ret;
    }

    void updateMin(int x) {
   
        while(x<=N) {
   
            C[x] = tim[x];
            for(int i=1;i<lowbit(x); i<<=1) C[x] = min(C[x], C[x-i]);
            x += lowbit(x); 
        }
    }

    void DEBUG() {
   
        for(int i = 1; i <= N; i++) {
   
            cout << i << ": " << C[i] << endl;
        }
    }
}Bit;


void handle(vector<pair<int, int> > &A,  int F[]) {
   
    Bit.init(2*(m1+m2) + 2);
    sort(A.begin(), A.end());
    memset(tim, 0x3f, sizeof(tim));
    memset(vis, 0, sizeof(vis));
    int cnt = 0;
    for(int i = 0; i < A.size(); i++) {
   
        int id = Bit.getMin(A[i].first);
        // 没有可以停靠的廊桥
        if(id == INF) {
   
            cnt ++;
            F[cnt] = 1;
            tim[A[i].second] = cnt;
            vis[cnt] = A[i].second;
            Bit.updateMin(A[i].second);
        }
        // 有可以停靠的廊桥
        else {
   
            tim[vis[id]] = INF;
            Bit.updateMin(vis[id]);
            vis[id] = A[i].second;
            tim[A[i].second] = id;
            Bit.updateMin(A[i].second);
            F[id] ++;
        }
        // Bit.DEBUG();
    }
}


vector<pair<int, int> > A1, A2;
int F1[MAXN], F2[MAXN];
vector<int> pool;
int main(){
   

    cin >> n >> m1 >> m2;
    for(int i = 0; i < m1; i++) {
   
        int l, r; cin >> l >> r;
        A1.push_back(make_pair(l, r));
        pool.push_back(l);
        pool.push_back(r);
    }
    for(int i = 0; i < m2; i++) {