6.CF431E Chemistry Experiment 权值线段树+二分

6.CF431E Chemistry Experiment 权值线段树+二分

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给定数列，区间查询和，区间取模，单点修改。
记录区间最大值，对于区间最大值小于模数的区间不予更新

洛谷传送门：CF431E Chemistry Experiment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Chemistry Experiment (codeforces.com)

题目分析

有$n$支试管，每支试管装有$h_{i}ml$的水银。
*
$q$次操作，操作有两种：

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

线段树上二分，维护权值线段树记录权值个数$siz$、权值和$cnt$。

二分时，对于当前的$mid$，判断 $mid\ast siz[l,mid]-cnt[l,mid]$ 与当前剩余水的大小关系，以此决定二分方向。

Code

#include 
#define int long long
#define double long double
#define endl '\n'
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
using namespace std;

const int N = 3e6 + 10, LEN = 1e7 + 10;
int h[N];
int n = 0, q = 0, root = 0;

namespace SegTree{
    #define lson ls[rt], l, mid
    #define rson rs[rt], mid + 1, r

    int tree[N][2], ls[N], rs[N], tot = 0;

    inline void push_up(int rt){ 
        tree[rt][0] = tree[ls[rt]][0] + tree[rs[rt]][0];
        tree[rt][1] = tree[ls[rt]][1] + tree[rs[rt]][1];
    }

    void update(int &rt, int l, int r, int pos, int val){
        if(!rt) rt = ++tot; 
        if(l == r){
            tree[rt][0] += val;
            tree[rt][1] += pos * val;
            return;
        }
        int mid = l + r >> 1;
        if(mid >= pos) update(lson, pos, val);
        else update(rson, pos, val);
        push_up(rt);
    }

    double search(int rt, int l, int r, int v){
        int siz = 0, cnt = 0;
        while(l != r){
            double mid = (l + r) / 2, val = mid * (siz + tree[ls[rt]][0]) - cnt - tree[ls[rt]][1];
            if(v < val) r = mid, rt = ls[rt];
            else{
                l = mid + 1, cnt += tree[ls[rt]][1], siz += tree[ls[rt]][0], rt = rs[rt];
            }
        }
        double ans = l + (v - (l * (siz + tree[ls[rt]][0]) - cnt - tree[ls[rt]][1])) * 1.0 / siz;
        return ans;
    }
}


#define SEGRG root, 0, 1e10

inline void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> h[i], SegTree::update(SEGRG, h[i], 1);
    while(q--){
        int op, v; cin >> op >> v;
        if(op == 1){
            int x; cin >> x;
            SegTree::update(SEGRG, h[v], -1);
            h[v] = x;
            SegTree::update(SEGRG, h[v], 1);
        } else {
            cout << SegTree::search(SEGRG, v) << endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76