【IOI2016】捷径 – 徐亦轲的博客

题意：有一条\(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)\)的。如果区间不为空则有解。

#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;
}

#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;

}