题目传送门
首先我们是可以把两个区拆开考虑的，以下以国内区为例：
我们先不考虑廊桥个数的限制。由于飞机是遵循先来先到的原则，所以我们不需要帮忙排飞机了，直接让飞机停在当前编号最小的空闲廊桥。
这样当每一班飞机到机场时，我们可以模拟出来这架飞机会停在哪个廊桥。
好，现在我们加上廊桥个数的限制。我们在考虑国内区的时候枚举当前分到的廊桥个数，如果分到了\(i\)个廊桥的话，那么\(i+1\)及以后的廊桥都可以被视作远机位了。
道理也很简单：如果这架飞机停在了\(i+1\)及往后的廊桥（假设为\(x\)），那么根据廊桥先来先得的原则，这架飞机能停的编号最小的廊桥也就是\(x\)了。也就是说，当只有\(i\)个廊桥时，它是无论如何都停不进去的。
这样一来，如果我们维护这个区里每个廊桥停的飞机数量（用\(num_j\)表示编号为\(j\)的廊桥能停多少个飞机），那么分到\(i\)个廊桥时，这个区就能停\(\sum\limits_{j=1}^{i} {num_j}\)个飞机。
很显然上面的累加和可以用前缀和数组优化。至此我们的思路就出来了：
首先将两个区拆开考虑，对于每个区，使用两个优先队列模拟飞机降落的过程。
具体来说，首先根据飞机到达时间升序排序，然后枚举\(1 - m1\)（国际区是\(1 - m2\)）内所有飞机，相当于是枚举每班飞机到达。这里我定义了两个优先队列，一个存储的是当前空闲廊桥编号（叫kx），按编号由小到大升序排序；另一个存储有飞机的廊桥（叫lq），共有两个信息，一个是当前停靠飞机的离开时间，一个是当前廊桥的编号。当第\(j\)架飞机到达时，首先比较lq队首的时间是否小于当前飞机的到达时间，如果是则说明该飞机已离开，将lq队首的廊桥编号扔到kx里，并将lq队首元素出栈。这样操作下来，已经离开的飞机都处理完了，接下来第\(j\)架飞机要进入的廊桥就是kx的队首元素（假设为\(x\)）。我们只要让\(num_x +1\)，并让kx将队首出队即可。
将两个区停靠情况模拟完成后，我们进行前缀和处理后（这里我国内区的前缀和数组为\(sum1\)，国际区为\(sum2\)），答案就是\(\max\limits_{i=0}^{n} sum1_i+sum2_{n-i}\)。
AC code:
#include<bits/stdc++.h>
#define int long long
#define mkp make_pair
#define l first
#define r second
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(c<48){if(c=='-') f=-1;c=getchar();}while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f;
}
const int N=1e5+5;
int n,m1,m2,num1[N],num2[N],sum1[N],sum2[N];
pair<int,int> a1[N],a2[N];
priority_queue<int,vector<int>,greater<int> > kx,kx1;
struct sw{int r,id;bool operator <(const sw SW)const{return r>SW.r;}
};
priority_queue<sw> lq;
signed main(){n=read(),m1=read(),m2=read();for(int i=1;i<=m1;i++){a1[i].l=read(),a1[i].r=read();}for(int i=1;i<=m2;i++){a2[i].l=read(),a2[i].r=read();}sort(a1+1,a1+m1+1);sort(a2+1,a2+m2+1);//按照航班的到达时间从小到大排序 for(int i=1;i<=n;i++){//初始所有廊桥均空 kx.push(i);}for(int i=1;i<=m1;i++){while(!lq.empty()&&lq.top().r<a1[i].l){//将已离开的飞机出队 kx.push(lq.top().id);lq.pop();}if(!kx.empty()){//像我这样把廊桥个数限制在1~n内的话，可能会出现所有廊桥都被停满的情况//因此我们需要if语句判断 num1[kx.top()]++;//飞机停入廊桥 lq.push((sw){a1[i].r,kx.top()});kx.pop();}}while(!lq.empty()){lq.pop();}while(!kx.empty()){kx.pop();}//如果两个区共用一套优先队列，记得重新初始化 for(int i=1;i<=n;i++){kx.push(i);//初始化，同上 }for(int i=1;i<=m2;i++){while(!lq.empty()&&lq.top().r<a2[i].l){kx.push(lq.top().id);lq.pop();}if(!kx.empty()){//同上num2[kx.top()]++;lq.push((sw){a2[i].r,kx.top()});kx.pop(); }}for(int i=1;i<=n;i++){//前缀和处理 sum1[i]=sum1[i-1]+num1[i];sum2[i]=sum2[i-1]+num2[i];}int ans=0;for(int i=0;i<=n;i++){//统计答案 ans=max(ans,sum1[i]+sum2[n-i]);}printf("%lld",ans);return 0;
}
)
