ARC069F Flags

题意：有$n$个旗子，第$i$个可以放在$x_i$或$y_i$，求它们两两之间最短距离的最大值 ------------ 二分答案+$2-SAT$+线段树优化 每个旗子要么放在$x_i$要么放在$y_i$，不难想到用$2-SAT$ 将$x_i$记为$i$号元素，$y_i$记为$i+n$号元素（对立点） 二分出一个最短距离$k$ 对于每个点二分出与它的权值差的绝对值小于$k$的区间$[l,r]$ 如果选择了这个区间中的点，那么这个点就不能选 这样就构造出了$2-SAT$模型 因为是区间向点连边，所以用线段树优化建图 总复杂度$O(nlog^2n)$ ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register #define reset(a) memset(a,0,sizeof(a)) using namespace std; typedef pair<int,int> par; const int N=1e5+5; struct E { int to,nxt; }edge[N*50]; struct node { int x,id; inline friend bool operator < (node a,node b) {return a.x<b.x;} }c[N]; int n,m,num,head[N],a[N],dfn[N],low[N],bel[N]; int cnt,tim,tot,stack[N],top,idx[N]; bool exist[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to) { edge[++num]=(E){to,head[from]}; head[from]=num; } inline void clear() { reset(dfn); reset(low); reset(bel); reset(exist); reset(head); reset(idx); num=cnt=tot=top=0; tim=n<<1; } void tarjan(int k) { int temp; dfn[k]=low[k]=++cnt; stack[++top]=k; exist[k]=1; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to; if (!dfn[v]) { tarjan(v); low[k]=min(low[k],low[v]); } else if (exist[v]) low[k]=min(low[k],dfn[v]); } if (dfn[k]==low[k]) { ++tot; do { temp=stack[top--]; exist[temp]=0; bel[temp]=tot; }while (temp!=k); } } void build(int l,int r,int now) { idx[now]=++tim; if (now>1) add_edge(idx[now>>1],tim); if (l==r) {add_edge(idx[now],c[l].id>n?c[l].id-n:c[l].id+n); return;} int mid=(l+r)>>1; build(l,mid,now<<1); build(mid+1,r,now<<1|1); } void change(int L,int R,int l,int r,int now,int x) { if (l>R||r<L) return; if (l>=L&&r<=R) {add_edge(x,idx[now]); return;} int mid=(l+r)>>1; if (mid>=R) change(L,R,l,mid,now<<1,x); else if (mid<L) change(L,R,mid+1,r,now<<1|1,x); else { change(L,mid,l,mid,now<<1,x); change(mid+1,R,mid+1,r,now<<1|1,x); } } inline par query(int p,int k) { par ret; ret.first=ret.second=p; int l=1,r=p,pos=p; while (l<=r) { int mid=(l+r)>>1; if (c[p].x-c[mid].x<k) pos=mid,r=mid-1; else l=mid+1; } ret.first=pos; l=p,r=m,pos=p; while (l<=r) { int mid=(l+r)>>1; if (c[mid].x-c[p].x<k) pos=mid,l=mid+1; else r=mid-1; } ret.second=pos; return ret; } inline bool check(int k) { clear(); build(1,m,1); for (reg int i=1;i<=m;i++) { par now=query(i,k); change(now.first,i-1,1,m,1,c[i].id); change(i+1,now.second,1,m,1,c[i].id); } for (reg int i=1;i<=m;i++) if (!dfn[i]) tarjan(i); for (reg int i=1;i<=n;i++) if (bel[i]==bel[i+n]) return 0; return 1; } int main() { n=read(); for (reg int i=1;i<=n;i++) { a[i]=read(),a[i+n]=read(); c[++m]=(node){a[i],i}; c[++m]=(node){a[i+n],i+n}; } sort(c+1,c+m+1); int l=0,r=1e9,ans=0; while (l<=r) { int mid=(l+r)>>1; if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); return 0; } ```