Codeforces 1469 F. Power Sockets —— 二分+线段树，贪心

This way

题意：

现在有一个根节点，和n条包含a[i]个节点的链。一开始所有点的颜色是白色的。你每次可以做以下操作：
找到树中某个白色节点，拿出一条链，将这个节点和链上某个节点连接，并且这两个点的颜色变成黑色，之后这条链属于树中一个部分。
你可以合并任意的链，问你离根节点第k远的白色点的深度最小是多少。

题解：

首先知道了一点：加入一条链的时候，两个白点会变成黑色，那么长度小于等于2的必不用加入。
并且长的链在前面一定是更优的，因为短链在前，再加长链的话，会使得更多的白点深度增加。
链接树上的白点时，一定是找深度最小的，连接链的时候，一定是链最中间的点。就像刚才说的一样，如果不是深度最小的话，更多的白点深度会增加。连接中间点的话，链上会有一半的点的深度降低。
但是我们不能白点数量一到k的时候就结束操作，因为可能能够在一些深度较低的白点上加链使得第k远的白点的深度减小。
于是这种最大值最小的题目我们一眼就知道是二分。
那么怎么知道当前第k远的点的深度，怎么知道深度最低的点的位置呢，使用线段树维护即可。

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+5;
#define ll long long 
ll sum[N*4],f[N*4];
void push_down(int l,int r,int root){
    if(!f[root])return ;
    int mid=l+r>>1;
    sum[root<<1]+=(mid-l+1)*f[root];
    sum[root<<1|1]+=(r-mid)*f[root];
    f[root<<1]+=f[root];
    f[root<<1|1]+=f[root];
    f[root]=0;
}
void update(int l,int r,int root,int ql,int qr,int v){
    if(l>=ql&&r<=qr){
        sum[root]+=(r-l+1)*v;
        f[root]+=v;
        return ;
    }
    int mid=l+r>>1;
    push_down(l,r,root);
    if(mid>=ql)
        update(l,mid,root<<1,ql,qr,v);
    if(mid<qr)
        update(mid+1,r,root<<1|1,ql,qr,v);
    sum[root]=sum[root<<1]+sum[root<<1|1];
}
int q_k(int l,int r,int root,int k){
    if(l==r)return l;
    int mid=l+r>>1;
    push_down(l,r,root);
    if(sum[root<<1]>=k)return q_k(l,mid,root<<1,k);
    else return q_k(mid+1,r,root<<1|1,k-sum[root<<1]);
}
int q_f(int l,int r,int root){
    if(l==r)return l;
    int mid=l+r>>1;
    push_down(l,r,root);
    if(sum[root<<1])return q_f(l,mid,root<<1);
    else return q_f(mid+1,r,root<<1|1);
}
int a[N],n,k;
bool cmp(int x,int y){return x>y;}
int check(int x){
    memset(sum,0,sizeof(sum)),memset(f,0,sizeof(f));
    update(1,N-1,1,2,1+(a[1]-1)/2,2);
    if(a[1]%2==0)
        update(1,N-1,1,1+a[1]/2,1+a[1]/2,1);
    for(int i=2;i<=n;i++){
        if(sum[1]>=k)
            if(q_k(1,N-1,1,k)<=x)return 1;
        if(a[i]<=2)return 0;
        int p=q_f(1,N-1,1);
        update(1,N-1,1,p,p,-1);
        update(1,N-1,1,p+2,min(N-1,p+1+(a[i]-1)/2),2);
        if(a[i]%2==0&&p+1+a[i]/2<=N-1)
            update(1,N-1,1,p+1+a[i]/2,p+1+a[i]/2,1);
    }
    if(sum[1]>=k)
        if(q_k(1,N-1,1,k)<=x)return 1;
    return 0;
}
int main()
{
    
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n,cmp);
    if(a[1]==2)return 0*printf("-1\n");
    int l=1,r=N-1,mid,ans=-1;
    while(r>=l){
        mid=l+r>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d\n",ans?ans:-1);
    return 0;
}