Tarjan 出大问题

#include <bits/stdc++.h>//喵内～
#define re register//喵内～
#define int long long
using namespace std;//喵内～
typedef long long ll;
typedef long double ld;
const int N = 2e4 + 5;//喵内～要填数字哟～
inline int read(){
    int s = 0,f = 1;char c = getchar();
    while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
    while (isdigit(c)){s = (s<<3) + (s<<1) + (c ^ 48);c = getchar();}
    return s * f;
}//喵内～
int n;
struct node{
	int val,id;
	friend bool operator < (const node x,const node y){
		return x.val < y.val;
	}
}a[N];
struct TernaryTree{
	int v,next;
}tree[N * 30];
int head[N * 10];
int dfn[N * 10],low[N * 10],ins[N * 10],color[N * 10],cnt,timer,num;
int id[N * 10];
int sccCnt;
stack<int> st;
int op(int x){if (x > n)return x - n;return x + n;}
void add(int u,int v){
	tree[++cnt].next = head[u];
	tree[cnt].v = v;
	head[u] = cnt;
}
void build(int rt,int l,int r){
	if (l > r)
	    return ;
	id[rt] = ++num;
	if (l == r){
		add(id[rt],op(a[l].id));
		return ;
	}
	int mid = (l + r) / 2;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	add(id[rt],id[rt << 1]);
	add(id[rt],id[rt << 1 | 1]);
}
void tarjan(int u){
	dfn[u] = low[u] = ++timer;
	ins[u] = 1;
	st.push(u);
	for (int i=head[u];i;i=tree[i].next){
		int v = tree[i].v;
		if (!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		} else if (ins[v]){
			low[u] = min(low[u],dfn[v]);
		}
	}
	if (dfn[u] == low[u]){
		++sccCnt;
		int s = 0;
		do{
			int s = st.top();st.pop();
			color[s] = sccCnt;ins[s] = 0;
		}while (s != u);
	}
}
void addEdge(int rt,int l,int r,int x,int y,int opp){
	if (l > r)
	    return ;
	if (l > y || r < x)
	    return ;
	if (l >= x && r <= y){
		add(opp,id[rt]);
		return ;
	}
	int mid = (l + r) / 2;
	addEdge(rt << 1,l,mid,x,y,opp);
	addEdge(rt << 1 | 1,mid + 1,r,x,y,opp);
}
int check(int d){
	while (!st.empty())
	   st.pop();
	memset(color,0,sizeof(color));
	memset(ins,0,sizeof(ins));
	memset(tree,0,sizeof(tree));
	memset(dfn,0,sizeof(dfn));
	memset(head,0,sizeof(head));timer = 0;cnt = 0;sccCnt = 0;num = 2 * n;
    build(1,1,2 * n);
    cout << "finish building" << endl;
	for (int i=1;i<=2*n;i++){
		int l = upper_bound(a+1,a+n*2+1,(node){a[i].val - d,0}) - a;
		int r = upper_bound(a+1,a+n*2+1,(node){a[i].val + d - 1,0}) - a - 1;
		addEdge(1,1,2*n,l,i-1,a[i].id);addEdge(1,1,2*n,i+1,r,a[i].id);
	}
	cout << "finish adding sides" << endl;
	for (int i=1;i<=2*n;i++)
	    if (!dfn[i])
	        cout << "doing " << i << endl,tarjan(i);
	cout << "finish coloring" << endl;
	for (int i=1;i<=n;i++)
	    if (color[i] == color[i + n])
	        return 0;
	return 1;
}
signed main(){
	n = read();
	for (int i=1;i<=n;i++){
        a[i].val = read();a[i].id = i;
		a[i + n].val = read(); a[i + n].id = i + n;	
	}
	sort(a+1,a+2*n+1);
    int l = 1,r = a[2 * n].val - a[1].val,ans = 0;
    while (l <= r){
    	int mid = l + r >> 1;
    	cout << mid << endl;
    	if (check(mid))
    	    ans = mid,l = mid + 1;
    	else r = mid - 1;
	}
	cout << ans << endl;
    return 0;
}//喵内～
/*
*/