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