MnZn第一次写主席树优化，样例不过求调

#include<bits/stdc++.h>
using namespace std;
#define N 100010
int n,m,dfn[N],low[N],scc[N],tot,dfc,sk[N],top,v[N],L,R,ans=-1,cnt,rt[5];
int id0[N],id1[N],id2[N],id3[N],hs[N];
bool in_sk[N];
struct number{int id,val;}a[N];

bool cmp1(number x,number y){
	if(x.val==y.val)return x.id<y.id;
	return x.val<y.val;
}
bool cmp2(number x,number y){return x.id<y.id;}
struct edge{int x,y;}r[N];
vector<int>p[N];
void tarjan(int x){
	dfn[x]=low[x]=++dfc;
	sk[++top]=x,in_sk[x]=1;
	for(int y:p[x]){
		if(!dfn[y]){
			tarjan(y);
			low[x]=min(low[x],low[y]);
		}else if(in_sk[y]){
			low[x]=min(low[x],dfn[y]);
		}
	}
	if(dfn[x]==low[x]){
		int t;++tot;
		do{
			t=sk[top--];
			scc[t]=tot,in_sk[t]=0;
		}while(t!=x);
	}
}
struct persistent_segments_tree{int lson,rson;}tr[N][4];
void insert(int &now,int x,int fa,int l,int r,int where,int &name,int opt){
	now=++cnt,tr[now][opt]=tr[x][opt];
	if(x&&opt<=1)p[cnt].push_back(x);
	else if(x)p[x].push_back(cnt);
	if(fa&&opt<=1)p[fa].push_back(now);
	else if(fa)p[now].push_back(fa);
	if(l==r){name=now;return;}
	int mid=(l+r)>>1,t=now;
	if(where<=mid)insert(tr[now][opt].lson,tr[x][opt].lson,t,l,mid,where,name,opt);
	else insert(tr[now][opt].rson,tr[x][opt].rson,t,mid+1,r,where,name,opt);
}
void add_edge(int now,int l,int r,int L,int R,int name,int opt){
	if(r<L||R<l||!now)return;
	if(L<=l&&r<=R){
		if(opt<2)p[name].push_back(now);
		else p[now].push_back(name);
		return;
	}
	int mid=(l+r)>>1;
	add_edge(tr[now][opt].lson,l,mid,L,R,name,opt);
	add_edge(tr[now][opt].rson,mid+1,r,L,R,name,opt);
}
bool check(int x){
	rt[0]=rt[1]=rt[2]=rt[3]=0;
	for(int i=1;i<=cnt;i++){
		p[i].clear(),id1[i]=id2[i]=id0[i]=id3[i]=scc[i]=0;
		dfn[i]=low[i]=in_sk[i]=0;
		for(int j=0;j<2;j++)
			tr[i][j].lson=tr[i][j].rson=0;
	}
	cnt=0,top=0,tot=0,dfc=0;
	for(int i=1;i<=n;i++){
		insert(rt[0],rt[0],0,1,n,v[i],id0[i],0);//选A，出树
		insert(rt[1],rt[1],0,1,n,v[i],id1[i],1);//选B，出树
		insert(rt[2],rt[2],0,1,n,v[i],id2[i],2);//选A，入树
		insert(rt[3],rt[3],0,1,n,v[i],id3[i],3);//选B，入树
		p[id2[i]].push_back(id0[i]);
		p[id3[i]].push_back(id1[i]);
		int les=upper_bound(hs+1,hs+1+n,a[i].val-x)-hs-1;//单点选A，区间选B
		int up=lower_bound(hs+1,hs+1+n,a[i].val+x)-hs;
		if(les>=1)add_edge(rt[1],1,n,1,les,id2[i],1),add_edge(rt[3],1,n,1,les,id0[i],3);
		if(up<=n)add_edge(rt[0],1,n,up,n,id3[i],0),add_edge(rt[2],1,n,1,les,id1[i],2);
	}
	for(int i=1;i<=m;i++)p[id2[r[i].x]].push_back(id1[r[i].y]),p[id2[r[i].y]].push_back(id1[r[i].x]);
	for(int i=1;i<=m;i++)p[id3[r[i].x]].push_back(id0[r[i].y]),p[id3[r[i].y]].push_back(id0[r[i].x]);
	for(int i=1;i<=cnt;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++){
		if(scc[id1[i]]==scc[id2[i]]){return 0;}
	}
	return 1;
}


signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>v[i],a[i].id=i,a[i].val=v[i],hs[i]=v[i];
	sort(a+1,a+1+n,cmp1),sort(hs+1,hs+1+n);
	for(int i=1;i<=n;i++)v[a[i].id]=i;
	sort(a+1,a+1+n,cmp2);
	for(int i=1;i<=m;i++)cin>>r[i].x>>r[i].y;
	L=1,R=1e9;
	while(L<=R){
		int mid=(L+R)>>1;
		if(check(mid))ans=mid,R=mid-1;
		else L=mid+1;
	}
	cout<<ans;
	return 0;
}