对于 本帖 中提到的错解（复杂度为 $n\sqrt n \log^2 n$）有如下 hack。

生成代码：

#include<bits/stdc++.h>
#define getchar() getchar_unlocked();
#define lb(x) (x&-x)
#define endl "\n"
using namespace std;

signed main(){
	int n = 200000,m = 200000;
	freopen("hack1.in","w",stdout);
	srand(time(0));
	printf("%d %d\n",n,m);
	for(int i = 0;i<n/4;i++){
		printf("%d ",i);
	}
	for(int i = 0;i<n/4;i++){
		printf("%d ",i);
	}
	for(int i = 0;i<n/2;i++){
		printf("%d ",i);
	}
	cout<<"\n";
	for(int i = 1;i<=m-4;i++){
		int l = rand()%(n-1)+1;
		printf("%d %d\n",l,rand()%(n-l)+l+1);
	}
	printf("1 100000\n100000 200000\n1 200000\n 199999 200000\n");
	return 0;
}