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 n n支试管，每支试管装有 h i   m l h_i\ ml hi​ ml的水银。 * q q q次操作，操作有两种：

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

线段树上二分，维护权值线段树记录权值个数 s i z siz siz、权值和 c n t cnt cnt。

二分时，对于当前的 m i d mid mid，判断 m i d ∗ s i z [ l , m i d ] − c n t [ l , m i d ] mid * siz[l, mid] - cnt[l, mid] mid∗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 > n >> q;
    for(int i = 1; i > 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