本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-05 10:20:36

Link

感觉就很扫描线。

需要注意这里全部都是小于号，不能取等，在离散化的时候需要注意加入 $x-1$ 和 $x+1$ 。在扫描线的时候也要特别注意一下边界问题。

还有一个细节是需要初始化，因为答案对应贡献可能为 $0$ ，这时需要初始化为 $\{0,1\}$ 。

注意左右端点不能取等。

(一开始写了一个酷似扫描线的枚举左端点求最优右端点的一个东西，但是挂了，调不出来)

code

const int N=6e5+5;

struct Seg_Tree{
	int t[N<<2],tag[N<<2],c[N<<2];
	void pushup(int x){
		if(t[ls]>=t[rs])
			c[x]=c[ls],t[x]=t[ls];
		else
			c[x]=c[rs],t[x]=t[rs];
	}
	void pushdown(int x){
		t[ls]+=tag[x];
		tag[ls]+=tag[x];
		t[rs]+=tag[x];
		tag[rs]+=tag[x];
		tag[x]=0;
	}
	void update(int x,int l,int r,int L,int R,int a){
		if(L<=l&&r<=R){
			t[x]+=a;
			tag[x]+=a;
			return;
		}
		if(tag[x]!=0)
			pushdown(x);
		if(L<=mid)
			update(ls,l,mid,L,R,a);
		if(R>mid)
			update(rs,mid+1,r,L,R,a);
		pushup(x);
	}
	void build(int x,int l,int r){
		tag[x]=t[x]=0;
		if(l==r)
			c[x]=l;
		else{
			build(ls,l,mid);
			build(rs,mid+1,r);
			pushup(x);
		}
	}
}T;

struct upd{
	int l,r,x,w;
	bool operator<(upd ano)const{
		return x<ano.x;
	}
}Q[N];
int tot;

int X[N],len; 

int l[N],r[N];

signed main(){
	int n=read(),limit=1e9;
	for(int i=1;i<=n;i++){
		l[i]=read(),r[i]=read();
		X[++len]=l[i],X[++len]=r[i];
		X[++len]=min(limit,l[i]+1),X[++len]=max(0ll,l[i]-1);
		X[++len]=min(limit,r[i]+1),X[++len]=max(0ll,r[i]-1);
	}
	X[++len]=0,X[++len]=limit;
	sort(X+1,X+1+len);
	len=unique(X+1,X+1+len)-X-1;
	T.build(1,1,len);
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(X+1,X+1+len,l[i])-X;
		r[i]=lower_bound(X+1,X+1+len,r[i])-X;
		if(l[i]>1&&l[i]+1<=r[i]-1){
			Q[++tot]={l[i]+1,r[i]-1,1,1};
			Q[++tot]={l[i]+1,r[i]-1,l[i],-1};
		}
		if(r[i]<len){
			Q[++tot]={r[i]+1,len,l[i]+1,1};
			Q[++tot]={r[i]+1,len,r[i],-1};
		}
	}
	sort(Q+1,Q+1+tot);
	pir ans={0,1};
	int mx=0;
	for(int i=1,j=1;i<=len;i++){
		while(j<=tot&&Q[j].x==i){
			T.update(1,1,len,Q[j].l,Q[j].r,Q[j].w);
			j++;
		}
		if(mx<T.t[1]){
			ans={X[i],X[T.c[1]]};
			mx=T.t[1];
		}
	}print(ans.fi),pc(' '),print(ans.se),pc('\n');
	return 0;
}