[题解] CF431E Chemistry Experiment

· · 题解

\color{red}博客内食用效果更佳（点我）

题外话

又被 long long 卡半天，为了警示自己，写一篇题解。

思路：（动态开点权值线段树）线段树+二分

复杂度：O(m\log^2(n))

主体思路

首先很显著从水银少的试管向水银多的试管依次取，并且最终倒完水后所有试管里的液面相平。

考虑将倒水分为两部分，先用水将所选的试管都填到同一高度（所选的试管水银高度中的最大值），然后如果有剩余则平均填到每一个试管中。先考虑暴力从前向后枚举选前 i 个水银最少的试管。如果 i-1 倒完水后的液面高于 i，那么将 i 选中显著是更优的，否则更劣。

排序后暴力枚举的话显然不支持修改，考虑权值线段树维护，因为空间限制需要动态开点。

如果选中前 i 个水银最少的试管劣于选 i-1 个，那么再向后选都不会更优，考虑直接二分选择前多少个试管，尝试找到最大的 i 使得选前 i 为更优的策略。

具体实现

线段树节点需要维护：

线段树需要支持：

对于 mid：设 pos 为第 mid 个试管的水银高度，q 为前 mid 个试管水银的和，x 为查询的值。

代码实现需要注意的地方：

参考代码：

参考代码中变量名与题解中均一致，详见注释。

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=1e5+5;

int n,m;
LL a[N];
//--------------------//
const int TN=N<<6;
struct Seg_Tree
{
    struct Seg_Tree_Node
    {
        int ls,rs;
        int cnt;
        LL val;
    }t[TN];
    int tot,root;

    void push_up(int rt){t[rt].cnt=t[t[rt].ls].cnt+t[t[rt].rs].cnt,t[rt].val=t[t[rt].ls].val+t[t[rt].rs].val;}

    void change(int &rt,int L,int R,int pos,int val)
    {
        if(!rt)
            rt=++tot;
        if(L==R)
        {
            t[rt].cnt+=val;
            t[rt].val+=1LL*val*L;
            return;
        }
        int mid=L+R>>1;
        if(pos<=mid)
            change(t[rt].ls,L,mid,pos,val);
        else
            change(t[rt].rs,mid+1,R,pos,val);
        push_up(rt);
        return;
    }

    LL query(int &rt,int L,int R,int rk)//查询前 rk 个的和
    {
        if(!rt)
            return 0;
        if(rk==t[rt].cnt)
            return t[rt].val;
        if(L==R)
            return L*rk;
        int mid=L+R>>1;
        LL res=0;
        res=query(t[rt].ls,L,mid,min(rk,t[t[rt].ls].cnt));//查左区间
        if(rk>t[t[rt].ls].cnt)//若排名超过左侧区间的元素个数，查右区间
            res+=query(t[rt].rs,mid+1,R,rk-t[t[rt].ls].cnt);
        return res;
    }

    int queryrk(int &rt,int L,int R,int rk)//查询第 rk 个的高度
    {
        if(!rt)
            return 0;
        if(L==R)
            return L;
        int mid=L+R>>1;
        if(t[t[rt].ls].cnt>=rk)//在左区间
            return queryrk(t[rt].ls,L,mid,rk);
        return queryrk(t[rt].rs,mid+1,R,rk-t[t[rt].ls].cnt);//在右区间
    }
}T;
//--------------------//
double mim(LL x)//二分
{
    int l=1,r=n,res=0;
    while(l<=r)
    {
        int mid=l+r>>1,pos=T.queryrk(T.root,0,1e9,mid);
        LL q=T.query(T.root,0,1e9,mid);
        if(1LL*pos*mid-q>x)//若为劣解
            r=mid-1;
        else//否则为优解
            l=mid+1,res=mid;
    }
    if(!res)
        res=1;
    LL q=T.query(T.root,0,1e9,res);
    return 1.0*(q+x)/res;//液体总量除以试管个数为答案
}
//--------------------//    
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]),T.change(T.root,0,1e9,a[i],1);
    LL x;
    for(int op,i=1;i<=m;i++)
    {
        scanf("%d%lld",&op,&x);
        if(op==1)
        {
            T.change(T.root,0,1e9,a[x],-1);
            scanf("%lld",&a[x]);
            T.change(T.root,0,1e9,a[x],1);
        }
        else
            printf("%.5lf\n",mim(x));
    }
    return 0;
}