当初，我爱罗作为“祭品之力”，为了控制体内“一尾”的力量，他开始了无休止的修炼。 作为一个刚入门的忍者，我爱罗先是要学会控制“一尾”守鹤之砂，第一步当然是要学会合并砂团啦，当然了，肯定不是盲目的合并，所以他给一开始的n个砂团从1到n编号，然后，每次合并，他会选择两个砂团u和v，将u所在的砂团集合与v所在的砂团集合合并，然后他对合并后的集合进行以下计算： 将所有砂团的编号取出来，假设有k个砂团，编号分别为a[1],a[2]..a[k]，假设一开始所有数都在其数轴上对应的位置，我们要做的是让最大的数和最小的数相遇，并求相遇最小时间。 我们这样操作这些数： 每次操作可以选择两个数轴上相邻数交换，多个操作可以同时进行，但不能对一个数同时进行两个交换操作。 交换时间就是两个数在数轴上的距离，因为每个数一个单位时间移动一个单位距离，一个交换操作中途两个数不能停下来，不能改变交换对象，直到两个数交换了位置。 当最小的数和最大的数走到了相邻位置时，他们相遇的时间就是距离/2，因为交换中途就会相遇。 相遇完后，数的位置恢复原状。 下面举一个例子： 1..4……11….16..19 我们要让1和19相遇 首先让1、4和16、19交换，他们可以同时进行，而且恰好同时结束了。用时3个单位，然后变成下面这样： 4..1……11….19..16 接下来有两种情况： A方案： 先让1和11先交换，19不动，那么用时7个单位，然后变成下面这样： 4..11……1….19..16 再交换1和19，用时2.5个单位。 加起来是这样的：3+7+2.5=12.5 B方案： 先让11和19交换，1不动，那么用时五个单位，且变成下面这样： 4..1……19….11..16 再用1和19交换，所用的时间是3.5个单位。 加起来是这样的：3+5+3.5=11.5 很明显B方案更优。 所以最少用时是11.5。 看样子大家都读懂题意了。 现在我爱罗已经是风影了，为了考验你这个新晋的上忍，他决定以当初的难题来考验你。
考虑如何求一个序列a1..n的答案 对于所有j求min(max(aj-a1,an-aj+1)+(aj+1-aj)/2) 把max外面的加进去，设mid=(aj+1+aj)/2，则变成max(mid-a1,an-mid) 于是我们分类讨论mid-a1>an-mid和mid-a1<=an-mid的两种情况，于是用线段树维护。 区间维护： 个数，最大最小值，相邻两个数相加的最大最小值 信息合并自己脑补，查询也很简单，详见代码。
#include<cstdio> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef double db; const int maxn=50000+10,maxtot=maxn*20; int root[maxn],left[maxtot],right[maxtot],num[maxtot],sum[maxtot],num2[maxtot],sum2[maxtot],cnt[maxtot];//num min sum max int fa[maxn]; int i,j,k,l,t,n,m,tot,ca; db ans,now; int getfa(int x){ return fa[x]?fa[x]=getfa(fa[x]):x; } int build(int &x,int l,int r,int wz){ x=++tot; if (l==r){ cnt[x]=1; num[x]=sum[x]=l; num2[x]=1000000; sum2[x]=0; return x; } int mid=(l+r)/2; if (wz<=mid) build(left[x],l,mid,wz);else build(right[x],mid+1,r,wz); cnt[x]=1; num[x]=sum[x]=sum[left[x]]+sum[right[x]]; num2[x]=1000000; sum2[x]=0; return x; } int merge(int a,int b,int l,int r){ if (!a||!b) return a+b; int mid=(l+r)/2; left[a]=merge(left[a],left[b],l,mid); right[a]=merge(right[a],right[b],mid+1,r); cnt[a]=cnt[left[a]]+cnt[right[a]]; num[a]=min(num[left[a]],num[right[a]]); sum[a]=max(sum[left[a]],sum[right[a]]); num2[a]=min(num2[left[a]],num2[right[a]]); if (cnt[left[a]]&&cnt[right[a]]) num2[a]=min(num2[a],sum[left[a]]+num[right[a]]); sum2[a]=max(sum2[left[a]],sum2[right[a]]); if (cnt[left[a]]&&cnt[right[a]]) sum2[a]=max(sum2[a],sum[left[a]]+num[right[a]]); return a; } int find(int p,int l,int r,int v){ if (cnt[p]<2) return 1000000; if (cnt[p]==2) return num[p]+sum[p]; int mid=(l+r)/2; if (cnt[left[p]]>1&&sum2[left[p]]>=v) return find(left[p],l,mid,v); else if (cnt[left[p]]&&cnt[right[p]]&&sum[left[p]]+num[right[p]]>=v) return sum[left[p]]+num[right[p]]; else return find(right[p],mid+1,r,v); } int find2(int p,int l,int r,int v){ if (cnt[p]<2) return -1000000; if (cnt[p]==2) return num[p]+sum[p]; int mid=(l+r)/2; if (cnt[right[p]]>1&&num2[right[p]]<=v) return find2(right[p],mid+1,r,v); else if (cnt[left[p]]&&cnt[right[p]]&&sum[left[p]]+num[right[p]]<=v) return sum[left[p]]+num[right[p]]; else return find2(left[p],l,mid,v); } int main(){ num[0]=num2[0]=1000000; cnt[0]=0; scanf("%d",&ca); while (ca--){ scanf("%d",&n); fo(i,1,n) root[i]=0; fo(i,1,tot) left[i]=right[i]=0; tot=0; fo(i,1,n) build(root[i],1,n,i); fo(i,1,n) fa[i]=0; fo(i,1,n-1){ //printf("%d\n",i); scanf("%d%d",&j,&k); j=getfa(j); k=getfa(k); fa[k]=j; root[j]=merge(root[j],root[k],1,n); ans=(db)find(root[j],1,n,num[root[j]]+sum[root[j]])/2-num[root[j]]; now=sum[root[j]]-(db)find2(root[j],1,n,num[root[j]]+sum[root[j]])/2; if (now<ans) ans=now; printf("%.1lf\n",ans); } } }