题意:有一条\(n\)个点的链,每个点又连接了一个特殊点,每条边有一个距离。现在你可以在链上某两个点间连一条权值为\(c\)的边使得得到的基环外向树直径最小。
考虑二分答案。
令\(len_i\)为链上点到最左端点的距离(即\(l\)的前缀和),
假设二分出的答案为\(k\),那么要求存在一对点\(a,b\),使得对于所有的\(len_j-len_i+d_j+d_i>k(i<j)\),有\(|len_i-len_a|+|len_j-len_b|+d_i+d_j+c<=k\)。
绝对值不好处理,将绝对值分四种情况得到四个不等式,只要同时满足即可。
按照\(len_j+d_j\)的顺序枚举\(j\),那么对应的\(i\)在按照\(len_i-d_i\)排序的数组内一定是一段区间,且端点单调。只需要满足\(i<j\)即可。将二分下界设为最大的两个\(d\)的和即可保证\(i<=j\),再在查询的时候记录要求的值的次大值,如果最大值对应的位置正好是当前枚举的\(j\)那么用次大值更新答案。那么就能求出\(len_b+len_a\)以及\(len_b-len_a\)的范围。
于是枚举\(b\),对应的\(a\)也是一段区间。不断更新区间端点即可,次数也是\(O(n)\)的。如果区间不为空则有解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include "shortcut.h" #include <bits/stdc++.h> using namespace std; typedef long long lol; const int MAXN=1000010; const lol INF=1e17; lol len[MAXN]; int n,d[MAXN],c,id1[MAXN],id2[MAXN]; bool check(lol k){ lol A=-INF,B=INF,C=-INF,D=INF; int p=0; lol sb1=0,sb2=0,v1=INF,v2=INF; lol sb3=0,sb4=0,v3=INF,v4=INF; for(int i=0;i<n;i++){ int I=id1[i],P=id2[p]; for(;p<n&&len[P]-d[P]<len[I]+d[I]-k;P=id2[++p]){ if(len[P]-d[P]<v2)v2=len[P]-d[P],sb2=P; if(v2<v1)swap(v1,v2),swap(sb1,sb2); if(-len[P]-d[P]<v4)v4=-len[P]-d[P],sb4=P; if(v4<v3)swap(v3,v4),swap(sb3,sb4); } A=max(A,c-k+len[I]+d[I]-(sb3==I?v4:v3)); B=min(B,k-c+len[I]-d[I]+(sb1==I?v2:v1)); C=max(C,c-k-len[I]+d[I]-(sb3==I?v4:v3)); D=min(D,k-c-len[I]-d[I]+(sb1==I?v2:v1)); } int l=0,r=-1; for(int i=0;i<n;i++){ while(r+1<n&&len[r+1]<=min(B-len[i],len[i]-C))r++; while(l&&len[l-1]>=max(A-len[i],len[i]-D))l--; while(r>=0&&len[r]>min(B-len[i],len[i]-C))r--; while(l<n&&len[l]<max(A-len[i],len[i]-D))l++; if(l<=r)return 1; } return 0; } bool cmp1(int x,int y){return len[x]+d[x]<len[y]+d[y];} bool cmp2(int x,int y){return len[x]-d[x]<len[y]-d[y];} lol find_shortcut(int nn,vector<int> le,vector<int> dd,int cc){ n=nn;c=cc; for(int i=1;i<n;i++)len[i]=len[i-1]+le[i-1]; lol l=0,r=0;int ma=0,mb=0; for(int i=0;i<n;i++){ r+=(d[i]=dd[i]); if(d[i]>mb)mb=d[i]; if(mb>ma)swap(ma,mb); } l=ma+mb;r+=len[n-1]; for(int i=0;i<n;i++)id1[i]=i,id2[i]=i; sort(id1,id1+n,cmp1); sort(id2,id2+n,cmp2); while(l<r){ lol m=l+r>>1; if(check(m))r=m; else l=m+1; } return l; } |