洛谷 P7913 [CSP-S 2021] 廊桥分配 题解

题目描述请移步 https://www.luogu.com.cn/problem/P7913

• 题目简述
  

有一座机场，分为国际区和国外区，机场共有n个廊桥，国内国际分别有m1,m2架飞机，给定每架飞机抵达时刻a、离开时刻b
对于每架飞机，若该区仍有廊桥空闲，就必须停靠在廊桥，否则停靠远机位（数量足够）
求将n个廊桥分配给国内区和国际区，停靠廊桥的飞机最多有多少架

• 题目分析
  

首先注意到飞机是有后效性的，先到达的飞机可能会占用一个廊桥直到它离开，因此需要对每架飞机按到达时间进行排序

遍历每架飞机复杂度为 O(m1+m2) ，而 m1+m2 就达到了 10^5 级别
因此累加贡献部分的复杂度须为 O(log n)

• 解题思路
  

发现对于每架飞机，如果它在有 x 个廊桥时停靠廊桥，那么有 x+1 个廊桥时它必定停靠廊桥
点击查看证明

1. 假设 x=2 ，为方便，第i架飞机用 p[i] 来表示
3. 不管数据具体是什么，这两个廊桥的使用必定与下图相似
5. 廊桥1：p[1] --> p[3] -> p[4] ---------> p[9]
6. 廊桥2：p[2] ---------------> p[7]
7. （后面 “上一架飞机” 意为使用同一廊桥的上一架飞机）
9. 每架飞机后面跟的都是首个到达时间比它离开时间晚的飞机（不考虑其他廊桥的占用）
11. 若第 i 架飞机在两个廊桥时停靠廊桥，而三个廊桥时不停靠廊桥，则只可能其上一架飞机未停靠廊桥
13. 以此类推，只有第 i 架飞机上一架的上一架... 即首个停靠原第 i 架飞机所停靠的廊桥的飞机未停靠廊桥，才可能成立
15. 而新设一个廊桥并不影响原廊桥第一架停靠的飞机，因此这种情况不可能发生

复制代码

因此，每架飞机对答案的贡献，是一个 min_can~n 的区间（令 min_can 为最小的可让这架飞机停靠廊桥的廊桥数量）
考虑使用线段树、树状数组等 log n 级别的结构来解决
这是我们只需维护每架飞机的 "min_can" 就行了，这里分两种情况讨论
1.这架飞机(p)到达时有飞机(p[j])离开了，那么 min_can[x]=min_can[j]
2.这架飞机到达时没有飞机离开，则 min_can[x]=目前所有没离开的飞机的数量
要注意的是，一架飞机到达时可能有多架飞机离开，那么它之后的几架飞机仍可以从情况1转移

• 代码实现
  

[code]#include #include #include #include #include #define int long longusing namespace std;const int MAX=1e5+7;int n,m1,m2;pair  p1[MAX],p2[MAX];//飞机 //priority_queue升序priority_queue  q1,q2;// priority_queue  mc1,mc2;//所有离开的飞机,维护并找到最小的min_can int min_can1[MAX],min_can2[MAX];//最少多少个廊桥才能使第i架飞机降落在廊桥 int tr1[MAX],tr2[MAX];//树状数组 int lowbit(int x){        return x&-x;}void add1(int pos){        for(int i=pos;i=1;i-=lowbit(i)){                res+=tr2;        }        return res;}signed main(){        cin>>n>>m1>>m2;        n=min(n,m1+m2);        for(int i=1;i>p1.first>>p1.second;        }        for(int i=1;i>p2.first>>p2.second;        }        sort(p1+1,p1+m1+1);        sort(p2+1,p2+m2+1);//按first升序        memset(min_can1,0x3f,sizeof(min_can1));        memset(min_can2,0x3f,sizeof(min_can2));//初始化极大值         for(int i=1;i