可以线段树
查看原帖
可以线段树
217786
创新人士楼主2021/11/7 10:54
#include<bits/stdc++.h>
using namespace std; 
#define N 100005
#define INF 100005 
#define lson (root<<1)
#define rson ((root<<1)+1)
#define mid ((l+r)>>1)
int n,m1,m2;
struct S{
	int a;int b;
};
S in[N],un[N];
bool cmp(S x,S y)
{
	return x.a<y.a;
}
inline void read()
{
	cin>>n>>m1>>m2;
	for(int i=1;i<=m1;i++)
	{
		cin>>in[i].a>>in[i].b;
	}
	for(int i=1;i<=m2;i++)
	{
		cin>>un[i].a>>un[i].b;
	}	
	sort(un+1,un+m2+1,cmp);
	sort(in+1,in+m1+1,cmp);
}
int tree[N<<2];
inline void up(int root)
{
	tree[root]=min(tree[lson],tree[rson]);
}
void ex(int root,int d,int pos,int l,int r)
{	

	if(l==r)
	{
		tree[root]=d;
		return;
	}
	if(pos<=mid)
	{
		ex(lson,d,pos,l,mid);
	}
	else
	{
		ex(rson,d,pos,mid+1,r);
	}
	up(root);
}
bool fl;
int fi(int root,int d,int l,int r)
{
//	if(fl)
//	cout<<root<<' '<<d<<' '<<l<<' '<<r<<' '<<tree[root]<<endl;
	if(l==r)
	return l;
	if(tree[lson]<=d)
	return fi(lson,d,l,mid);
	else
	return fi(rson,d,mid+1,r);
}
void init(int root,int l,int r)
{
	tree[root]=0;
	if(l==r)return;
	init(lson,l,mid);
	init(rson,mid+1,r);
}
int s1[N],s2[N],l1,l2;
void solve()
{
	
	int now;
	for(int i=1;i<=m1;i++)
	{
		now=fi(1,in[i].a,1,N-5);
		s1[now]++;
		ex(1,in[i].b,now,1,N-5);
	//	cout<<now<<' '<<in[i].a<<endl; 
	}
	init(1,1,N-5);
	for(int i=1;i<=m2;i++)
	{
		now=fi(1,un[i].a,1,N-5);
		s2[now]++;
		ex(1,un[i].b,now,1,N-5);
	}
	
/*	for(int i=1;i<=n;i++)
	{
		cout<<s1[i]<<' ';
	}
	
	cout<<endl;
	
	for(int i=1;i<=n;i++)
	{
		cout<<s2[i]<<' ';
	}*/
	int s=0,ans=0;
	for(int i=1;i<=n;i++)
	s+=s1[i];
	ans=s;
	for(int i=1;i<=n;i++)
	{
		s=s+s2[i]-s1[n-i+1];
		ans=max(ans,s);
	}
//	cout<<endl;
	cout<<ans;
}
signed main()
{
	read();
	solve();
}
2021/11/7 10:54
加载中...