[??记录]AT2336 [ARC069D] Flags

**题意** ： 将 $N$ 个标志放在数轴上。第 $i$ 个标志可以放置在坐标 $a_i$ 或 $b_i$ 上。 求出两个标志之间最小距离的最大值。 $n\leq 10^4$ ，时限$\texttt{5s}$。 ------------ 先二分答案，然后用 $\text{2-sat}$ 判定。 枚举点标志 $i$ ，对于另标志 $j$ ，按如下规则连边。 - $|a_i-a_j|\leq mid$ : $a_i\rightarrow b_j$ - $|b_i-a_j|\leq mid$ : $b_i\rightarrow b_j$ - $|a_i-b_j|\leq mid$ : $a_i\rightarrow a_j$ - $|b_i-b_j|\leq mid$ : $b_i\rightarrow a_j$ 缩点后，若 $a_i,b_i$ 在同一个联通块内，则无解。 不难用（两颗）线段树优化建边。复杂度为 $O(n\log^2 n)$。 常数大得有点离谱…… ```cpp #include<algorithm> #include<cstdio> #define ll long long #define MaxN 10500 using namespace std; struct Line{int t,nxt;}l[MaxN*200]; int fir[MaxN*4],tl; void adl(int u,int v) {l[++tl]=(Line){v,fir[u]};fir[u]=tl;} int dfn[MaxN*4],low[MaxN*4],tim,stk[MaxN*4],top,col[MaxN*4],Bcnt; void tar(int u) { dfn[stk[++top]=u]=low[u]=++tim; for (int i=fir[u],v;i;i=l[i].nxt) if (!dfn[v=l[i].t]) {tar(v);low[u]=min(low[u],low[v]);} else if (!col[v])low[u]=min(low[u],dfn[v]); if (low[u]==dfn[u]){ Bcnt++; while(stk[top+1]!=u) col[stk[top--]]=Bcnt; } } int wfl,wfr,wfc,tn,n; struct SGT { int p[MaxN<<2],lp[MaxN]; void build(int l=1,int r=n,int u=1) { if (l==r){p[u]=lp[l];return ;} int mid=(l+r)>>1;p[u]=++tn; build(l,mid,u<<1); build(mid+1,r,u<<1|1); adl(p[u],p[u<<1]);adl(p[u],p[u<<1|1]); } void add(int l=1,int r=n,int u=1) { if (wfl<=l&&r<=wfr){adl(wfc,p[u]);return ;} int mid=(l+r)>>1; if (wfl<=mid)add(l,mid,u<<1); if (mid<wfr)add(mid+1,r,u<<1|1); } }Ta,Tb; int a[MaxN],b[MaxN],xa[MaxN],xb[MaxN],ta[MaxN],tb[MaxN]; bool chk(int lim) { for (int i=1;i<=tn;i++)dfn[i]=fir[i]=col[i]=0; tl=0;tn=2*n; Ta.build();Tb.build(); for (int i=1;i<=n;i++){ wfc=i; int l=a[i]-lim+1,r=a[i]+lim-1,mid=ta[i]; wfl=lower_bound(xa+1,xa+n+1,l)-xa;wfr=mid-1; if (wfl<=wfr)Ta.add(); wfl=mid+1;wfr=upper_bound(xa+1,xa+n+1,r)-xa-1; if (wfl<=wfr)Ta.add(); wfl=lower_bound(xb+1,xb+n+1,l)-xb; wfr=upper_bound(xb+1,xb+n+1,r)-xb-1; if (wfl<=wfr)Tb.add(); wfc=i+n; l=b[i]-lim+1,r=b[i]+lim-1; wfl=lower_bound(xa+1,xa+n+1,l)-xa; wfr=upper_bound(xa+1,xa+n+1,r)-xa-1; if (wfl<=wfr)Ta.add(); mid=tb[i]; wfl=lower_bound(xb+1,xb+n+1,l)-xb;wfr=mid-1; if (wfl<=wfr)Tb.add(); wfl=mid+1;wfr=upper_bound(xb+1,xb+n+1,r)-xb-1; if (wfl<=wfr)Tb.add(); } for (int i=1;i<=2*n;i++) if (!dfn[i])tar(i); for (int i=1;i<=n;i++) if (col[i]==col[i+n])return 0; return 1; } bool cmpA(int A,int B){return a[A]<a[B];} bool cmpB(int A,int B){return b[A]<b[B];} int main() { scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d%d",&a[i],&b[i]); xa[i]=a[i];xb[i]=b[i]; Ta.lp[i]=Tb.lp[i]=i; } sort(Ta.lp+1,Ta.lp+n+1,cmpA);sort(Tb.lp+1,Tb.lp+n+1,cmpB); for (int i=1;i<=n;i++){ ta[Ta.lp[i]]=tb[Tb.lp[i]]=i; Ta.lp[i]+=n; }sort(xa+1,xa+n+1);sort(xb+1,xb+n+1); int l=0,r=1000000000,mid; while(l<r){ mid=(l+r+1)>>1; if (chk(mid))l=mid; else r=mid-1; }printf("%d",r); return 0; } ```