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

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

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

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

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

题目分析

有支试管，每支试管装有的水银。
*
次操作，操作有两种：

• ：倒掉试管的水银修改为。
• ：将水任意分配至支试管里，最小化有水的试管中最大体积，输出这个最小值，误差不超过算作正确。这个操作只是一次假想，不会真的把水倒进试管里。

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

二分时，对于当前的，判断

Code

#include <bits/stdc++.h>
#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,
    #define rson rs[rt], mid + 1,

    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;
}