CF431E Chemistry Experiment

题目大意

有\(n\)支试管，每支试管装有\(h_i\ ml\)的水银。

\(q\)次操作，操作有两种：

• 1 \(p\) \(x\)：倒掉试管\(p\)的水银修改为\(x\ ml\)。
• 2 \(v\)：将\(v\ ml\)水任意分配至\(n\)支试管里，最小化有水的试管中最大体积，输出这个最小值，误差不超过\(10^{-4}\)算作正确。。这个操作只是一次假想，不会真的把水倒进试管里。

\(n,q\le 10^5\)，\(0\le h_i,x\le 10^9\)，\(1\le v\le 10^{15}\)

分析

我们主要分析第二个操作，第一个操作比较基础。

我们先在不改变试管液体体积的情况下考虑如果我们想最小化有水的试管中的最大体积。我们就要尽可能的选择体积小的试管加水，同时我们需要考虑，是否需要继续加入新的试管。那这个怎么考虑呢，先对所有试管进行排序，如果此时我们选择的前i个管子的总和的液体平均值大于等于第i+1个管子的溶液量，那就可以把第i+1个管子选上。同时，我们可以发现，这个选择具有二分性，则我们可以通过二分找到这个管子。

现在我们将改变试管体积的条件加上，我们考虑离线，先将所有可能出现的溶液体积记录下来。然后排一个序。

此时，我们就知道了，不同体积对应的编号。但是如果体积相同怎么办呢？体积相同，我们就用哈希表分别记录不同类别(指是新加的溶液还是之前就有的)的不同编号的溶液体积在新的编号下是哪个，方便我们修改。

这样，我们如果想求合适的体积，就可以在新的编号建立的树状数组上动态的求出不断改变的数组下标的和，与此时这个范围内所对应的数字总数。

同时，因为我们需要动态的知道，大于此时第i个瓶子溶液的溶液是多大体积，我们用一个set维护即可。

其实感觉说的不太明白，不过可以看看代码，就比较清晰了。

Ac_code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const double eps = 1e-10;
const int N = 2e5 + 10;

struct node//保存不同类型的不同编号所对应的值
{
    int x,ty,id;
};

struct Node//保存问题
{
    int op;
    LL x;
    int y;
}query[N];

LL tr1[N],tr2[N];//tr1维护和,tr2维护数量
int a[N];
multiset<int> s;//维护此时试管的所有溶液体积
vector<node> all;//重新设立新编号
map<int,int> mp[2];//记录不同类别不同编号的新编号
int n,q;

bool cmp(node &a,node &b)
{
    if(a.x==b.x&&a.id==b.id) return a.ty<b.ty;
    if(a.x==b.x) return a.id<b.id;
    return a.x<b.x;
}

void add(int x,int c,LL tr[])
{
    while(x<=all.size())
    {
        tr[x] += c;
        x += x & -x;
    }
}

LL sum(int x,LL tr[])
{
    LL res = 0;
    while(x)
    {
        res += tr[x];
        x -= x & -x;
    }
    return res;
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        int x;cin>>x;
        a[i] = x;s.insert(x);
        all.push_back({x,0,i});
    }
    for(int i=1;i<=q;i++) 
    {
        int op,y;
        LL x;cin>>op>>x;
        if(op==1) cin>>y;
        query[i] = {op,x,y};
        if(op==1) all.push_back({y,1,i});
    }
    sort(all.begin(),all.end(),cmp);
    for(int i=0;i<all.size();i++){
        if(!all[i].ty) add(i+1,all[i].x,tr1),add(i+1,1,tr2);
        mp[all[i].ty][all[i].id] = i + 1;
    }
    for(int i=1;i<=q;i++)
    {
        int op = query[i].op;
        LL x = query[i].x,y = query[i].y;
        if(op==1)
        {
            int t = mp[0][x];add(t,-a[x],tr1);add(t,-1,tr2);//先找到之前的体积的下标，将改下标对应的值在tr1中删除，同时将tr2中对应的位置删去
            s.erase(s.lower_bound(a[x]));s.insert(y);a[x] = y;//将原来的值删去，并加入新的值
            t = mp[0][x] = mp[1][i];//更新溶液中x号试管对应的新编号
            add(t,a[x],tr1);add(t,1,tr2);//将tr1，tr2中的新编号位置加上对应的值
        }
        else 
        {
            int l = 1,r = all.size();
            double ans = 1e18;
            while(l<r)//二分出合适的位置
            {
                int mid = l + r + 1>> 1;
                LL sum1 = sum(mid,tr1) + x,sum2 = sum(mid,tr2);
                double t = 1.0*sum1/sum2;
                ans = min(ans,t);
                double res = 1e18;
                auto it = s.lower_bound(all[mid-1].x);
                if(it!=s.end()) 
                {
                    int tmp = *it;
                    if(all[mid-1].x==tmp) ++it;
                    //这里卡了我好久，如果找到的值和此时mid处的试管体积一样，则代表我们找到了mid，但我们需要的mid的下一个，所以需要++。
                    //但我不是没想到++，我是忘记了，如果不相等的话，那直接就已经找到下一个了，就不用++了。
                    res = *it;
                }
                if(res<=t) l = mid;
                else r = mid - 1;
            }
            ans = min(ans,1.0*(sum(l,tr1)+x)/sum(l,tr2));
            printf("%.4lf\n",ans);
        }
    }
    return 0;
}