CF431E Chemistry Experiment 题解

题意：

有 $n$ 支试管，每支试管装有 $h_i\ \mathrm{ml}$ 的水银。

$q$ 次操作，操作有两种：

1 p x：倒掉试管 $p$ 的水银修改为 $x\ \mathrm{ml}$。

2 v：将 $v\ \mathrm{ml}$ 水任意分配至 $n$ 支试管里，最小化有水的试管中最大体积，输出这个最小值

误差不超过 $10^{-4}$ 算作正确（这个操作只是一次假想，不会真的把水倒进试管里）。

输入格式：

The first line contains two integers $n$ and $q$ ( $1\le n,q\le 10^{5}$ ) — the number of tubes ans the number of experiment steps. The next line contains $n$ space-separated integers: $h_{1},h_{2},\cdots,h_{n}$ ( $0\le h_{i}\le 10^{9}$ ), where $h_{i}$ is the volume of mercury in the $і$ -th tube at the beginning of the experiment.

The next $q$ lines contain the game actions in the following format:

A line of form $1\ p_{i}\ x_{i}$ means an action of the first type ( $1\le p_{i}\le n,~ 0\le x_{i}\le 10^{9}$ ).

A line of form $2\ v_{i}$ means an action of the second type ( $1\le v_{i}\le 10^{15}$ ).

It is guaranteed that there is at least one action of the second type. It is guaranteed that all numbers that describe the experiment are integers.

输出格式：

For each action of the second type print the calculated value. The answer will be considered correct if its relative or absolute error doesn’t exceed $10^{-4}$ .

数据范围：

$1\le n,q\le 10^5,~0\le h_i,x\le 10^9,~1\le v\le 10^{15}$ 。

容易发现，倒水一定是先倒水银较少的瓶子，如图所示（来自参考文献[1]）

考虑二分最终高度 $h$ ，令 $x$ 为满足 $a_x < h$ 的最大瓶子的下标，则体积应为

$V_e=\left(h-a_1\right)+\left(h-a_2\right)+\cdots+\left(h-a_x\right)=x h-\sum_{i=1}^x a_i$

若 $V > V_e$ ，则说明水还能倒，增大 $h$ 。反之减少 $h$ 。

然后这个 $a$ 是带修改的，考虑使用权值线段树维护，这样查询直接线段树上二分即可。

时间复杂度 $\mathcal{O}(n \log M)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define M ((int)(1e9 + 7))
#define ls(at) ch[at][0]
#define rs(at) ch[at][1]

int n,tot = 1,h[N],ch[N << 5][2],sum[N << 5],val[N << 5];
void add(int at,int l,int r,int h,int k)
{
    if(l == r) { val[at] += k; sum[at] += l * k; return; }
    int mid = (l + r) >> 1;
    if(h <= mid)
    {
        if(!ls(at)) ls(at) = ++tot;
        add(ls(at), l, mid, h, k);
    }else
    {
        if(!rs(at)) rs(at) = ++tot;
        add(rs(at), mid + 1, r, h, k);
    }
    val[at] = val[ls(at)] + val[rs(at)];
    sum[at] = sum[ls(at)] + sum[rs(at)];
}
double query(int at,int l,int r,int V)
{
    int mid, Ve, oc = 0, oV = 0;
    for(; l < r && at; )
    {
        mid = (l + r) >> 1;
        Ve = mid * (val[ls(at)] + oc) - (sum[ls(at)] + oV);
        if(V > Ve)
        {
            oc += val[ls(at)]; oV += sum[ls(at)];
            at = rs(at); l = mid + 1;
        }else { at = ls(at), r = mid; }
    }
    return (double)(V + oV) / (double) oc;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(8);
    int Q; cin >> n >> Q;
    for(int i = 1; i <= n; i++) { cin >> h[i]; add(1, 0, M, h[i], 1); }
    for(int op,x,y; Q--; )
    {
        if(cin >> op, op == 1)
        {
            cin >> x >> y;
            add(1, 0, M, h[x], -1);
            add(1, 0, M, h[x] = y, 1);
        }else
        {
            cin >> x;
            cout << query(1, 0, M, x) << '\n';
        }
    }
    return 0;
}