按照题意模拟即可。

每一次把当前飞机放到编号最小的空廊桥，记录每一个廊桥的贡献，记录一个前缀和，最后答案就是 $\max _{i=0}^n sum1_i+sum2_{n-i}$。

注意这个 $i$ 是要从 $0$ 到 $n$，因为有可能某一边一个也不用。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e>'9'||e<'0') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<3)+(x<<1)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=100005;
int n,m1,m2,ans;
struct node {
	int l,r;
} a[N];
bool cmp(node A,node B) {
	return A.l<B.l;
}
int u[N];// the i-th flight use u_i
bool vis[N];//is the i-th bridge using??
int cnt[N];//the i-th bridge has a profit of cnt_i
int sum[2][N];//pair<int,int>: leave time, the flight id
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > >q;
priority_queue<int,vector<int>,greater<int> > Q;
void f(int m,bool op) {
	while(!q.empty())q.pop();
	while(!Q.empty())Q.pop();
	memset(cnt,0,sizeof cnt);
	sort(a+1,a+1+m,cmp);
	for(int i=1; i<=m; ++i) Q.push(i);
	for(int i=1; i<=m; ++i) {
		while(!q.empty()&&q.top().first<=a[i].l) {
			Q.push(u[q.top().second]);
			vis[u[q.top().second]]=0;
			q.pop();
		}
		int nw=Q.top();
		Q.pop();
		u[i]=nw;
		vis[i]=1;
		++cnt[nw];
		q.push({a[i].r,i});
	}
	for(int i=1; i<=n; ++i) {
		sum[op][i]=sum[op][i-1]+cnt[i];
	}
}
signed main() {
	R(n),R(m1),R(m2);
	for(int i=1; i<=m1; ++i) R(a[i].l),R(a[i].r);
	f(m1,0);
	for(int i=1; i<=m2; ++i) R(a[i].l),R(a[i].r);
	f(m2,1);
	for(int i=0; i<=n; ++i) ans=max(ans,sum[0][i]+sum[1][n-i]);
	cout<<ans;
	return 0;
}

This problem is basically a warm-up Once you pass this, you're all set

First, we can straightforwardly write an $O(n^2)$ brute force solution

For each aircraft, find the smallest available gate that has already been vacated, and then consider placing the aircraft there

The reason for choosing the smallest number is that we aim to minimize the use of boarding bridges

Then, considering optimization, it was found that the bottleneck lies in assigning a boarding bridge to each aircraft while ensuring the smallest possible numbering

You can consider using a segment tree for binary search or binary search with a segment tree for querying. In fact, a dynamic segment tree can also be employed.

Both $O(n \times \log n)$ and $O(n \times \log^2 n)$ can pass this problem

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m1,m2,cnt=1,ans=0,pos[N],pre[N],cnt1[N],cnt2[N];
struct node{
	int l,r;
}a[N],b[N];
struct tree{
	int l,r,data;
}t[N<<4];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool cmp(node a,node b){return a.l<b.l;}
void pushup(int p){
	int x=p<<1,y=p<<1|1;
	t[p].data=min(t[x].data,t[y].data);
}
void builds(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].data=2e9;
	if(l==r) return;
	int mid=(l+r)>>1;
	int x=p<<1,y=p<<1|1;
	builds(x,l,mid),builds(y,mid+1,r);
	pushup(p);
}
void changes(int p,int l,int r,int d){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].data=d;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;
	if(l<=mid) changes(x,l,r,d);
	if(r>mid) changes(y,l,r,d);
	pushup(p);
}
int asks(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1,ans=2e9;
	if(l<=mid) ans=min(ans,asks(x,l,r));
	if(r>mid) ans=min(ans,asks(y,l,r));
	return ans;
} 
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m1=reads(),m2=reads();
		for(int i=1;i<=m1;i++) a[i].l=reads(),a[i].r=reads();
		for(int i=1;i<=m2;i++) b[i].l=reads(),b[i].r=reads();
		sort(a+1,a+m1+1,cmp),sort(b+1,b+m2+1,cmp);
		builds(1,1,100000);
		cnt1[1]++,changes(1,1,1,a[1].r);
		for(int i=2;i<=m1;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=a[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt1[++cnt]++,changes(1,cnt,cnt,a[i].r);
			else cnt1[res]++,changes(1,res,res,a[i].r);		
		}builds(1,1,100000);cnt=1;
		cnt2[1]++,changes(1,1,1,b[1].r);
		for(int i=2;i<=m2;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=b[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt2[++cnt]++,changes(1,cnt,cnt,b[i].r);
			else cnt2[res]++,changes(1,res,res,b[i].r);		
		}
		for(int i=1;i<=n;i++) cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
		for(int i=0;i<=n;i++) ans=max(ans,cnt1[i]+cnt2[n-i]);
		printf("%d\n",ans);
	}
	return 0;
}

這題算是簽到題了過了這題就1=

首先我們可以氫竦寫出 $O(n^2)$ 的暴力

暴力對於每一架飛機，找一個編號最小的、已經飛走的停機位，然後考慮把這架飛機放進去。

為什麼是編號最小，是因為我們考慮盡量小的使用廊 橋

接著考慮優化，發現瓶頸在於為每架飛機分配廊橋，且需保證編號最小。

可以考慮線段樹二分或者二分用線段樹查詢，事實上也可以使用動態開點線段樹

無論是 $O(n\times \log n)$ 還是 $O(n \times \log ^2 n)$ 都可以通過這道題

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m1,m2,cnt=1,ans=0,pos[N],pre[N],cnt1[N],cnt2[N];
struct node{
	int l,r;
}a[N],b[N];
struct tree{
	int l,r,data;
}t[N<<4];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool cmp(node a,node b){return a.l<b.l;}
void pushup(int p){
	int x=p<<1,y=p<<1|1;
	t[p].data=min(t[x].data,t[y].data);
}
void builds(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].data=2e9;
	if(l==r) return;
	int mid=(l+r)>>1;
	int x=p<<1,y=p<<1|1;
	builds(x,l,mid),builds(y,mid+1,r);
	pushup(p);
}
void changes(int p,int l,int r,int d){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].data=d;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;
	if(l<=mid) changes(x,l,r,d);
	if(r>mid) changes(y,l,r,d);
	pushup(p);
}
int asks(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1,ans=2e9;
	if(l<=mid) ans=min(ans,asks(x,l,r));
	if(r>mid) ans=min(ans,asks(y,l,r));
	return ans;
} 
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m1=reads(),m2=reads();
		for(int i=1;i<=m1;i++) a[i].l=reads(),a[i].r=reads();
		for(int i=1;i<=m2;i++) b[i].l=reads(),b[i].r=reads();
		sort(a+1,a+m1+1,cmp),sort(b+1,b+m2+1,cmp);
		builds(1,1,100000);
		cnt1[1]++,changes(1,1,1,a[1].r);
		for(int i=2;i<=m1;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=a[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt1[++cnt]++,changes(1,cnt,cnt,a[i].r);
			else cnt1[res]++,changes(1,res,res,a[i].r);		
		}builds(1,1,100000);cnt=1;
		cnt2[1]++,changes(1,1,1,b[1].r);
		for(int i=2;i<=m2;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=b[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt2[++cnt]++,changes(1,cnt,cnt,b[i].r);
			else cnt2[res]++,changes(1,res,res,b[i].r);		
		}
		for(int i=1;i<=n;i++) cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
		for(int i=0;i<=n;i++) ans=max(ans,cnt1[i]+cnt2[n-i]);
		printf("%d\n",ans);
	}
	return 0;
}

这道题算是签到题了过了这题就1=

首先我们可以氢竦写出 $O(n^2)$ 的暴力

暴力对于每一个飞机找一个编号最小的、已经飞走的机位然后考虑把这个飞机放进去

为什么是编号最小，是因为我们考虑尽可能小的使用廊桥

然后考虑优化，发现瓶颈在于给每一个飞机找廊桥，并且保证编号最小

可以考虑线段树二分或者二分用线段树查询，事实上也可以使用动态开点线段树

不管是 $O(n\times \log n)$ 还是 $O(n \times \log ^2 n)$ 都可以通过这道题

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
const int N=1e5+10;
int _=1,n,m1,m2,cnt=1,ans=0,pos[N],pre[N],cnt1[N],cnt2[N];
struct node{
	int l,r;
}a[N],b[N];
struct tree{
	int l,r,data;
}t[N<<4];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("airport.in","r",stdin);
	freopen("airport.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool cmp(node a,node b){return a.l<b.l;}
void pushup(int p){
	int x=p<<1,y=p<<1|1;
	t[p].data=min(t[x].data,t[y].data);
}
void builds(int p,int l,int r){
	t[p].l=l,t[p].r=r,t[p].data=2e9;
	if(l==r) return;
	int mid=(l+r)>>1;
	int x=p<<1,y=p<<1|1;
	builds(x,l,mid),builds(y,mid+1,r);
	pushup(p);
}
void changes(int p,int l,int r,int d){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].data=d;
		return;
	}
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1;
	if(l<=mid) changes(x,l,r,d);
	if(r>mid) changes(y,l,r,d);
	pushup(p);
}
int asks(int p,int l,int r){
	if(l<=t[p].l&&t[p].r<=r) return t[p].data;
	int mid=(t[p].l+t[p].r)>>1;
	int x=p<<1,y=p<<1|1,ans=2e9;
	if(l<=mid) ans=min(ans,asks(x,l,r));
	if(r>mid) ans=min(ans,asks(y,l,r));
	return ans;
} 
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m1=reads(),m2=reads();
		for(int i=1;i<=m1;i++) a[i].l=reads(),a[i].r=reads();
		for(int i=1;i<=m2;i++) b[i].l=reads(),b[i].r=reads();
		sort(a+1,a+m1+1,cmp),sort(b+1,b+m2+1,cmp);
		builds(1,1,100000);
		cnt1[1]++,changes(1,1,1,a[1].r);
		for(int i=2;i<=m1;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=a[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt1[++cnt]++,changes(1,cnt,cnt,a[i].r);
			else cnt1[res]++,changes(1,res,res,a[i].r);		
		}builds(1,1,100000);cnt=1;
		cnt2[1]++,changes(1,1,1,b[1].r);
		for(int i=2;i<=m2;i++){
			int L=1,R=cnt,res=0;
			bool flg=0;
			while(L<=R){
				int mid=(L+R)>>1;
				if(asks(1,1,mid)<=b[i].l) flg=1,res=mid,R=mid-1;
				else L=mid+1;
			}
			if(!flg) cnt2[++cnt]++,changes(1,cnt,cnt,b[i].r);
			else cnt2[res]++,changes(1,res,res,b[i].r);		
		}
		for(int i=1;i<=n;i++) cnt1[i]+=cnt1[i-1],cnt2[i]+=cnt2[i-1];
		for(int i=0;i<=n;i++) ans=max(ans,cnt1[i]+cnt2[n-i]);
		printf("%d\n",ans);
	}
	return 0;
}