牛客多校第九场 H Cutting Bamboos —— 主席树

题目链接：点我啊╭(╯^╰)╮

题目大意：

    给你一片竹林，编号 $1$ 到 $n$ ，给定初始高度
    每次查询区间，问一共砍 $y$ 刀的时候，第 $x$ 刀的高度
    要求 $y$ 刀砍完时区间全被砍完，切每刀切出来的量相等

解题思路：

    可求得第 $x$ 刀需要砍的量 $all$
    问题就转化为了 查询区间高于某个数的总量为 $all$
    主席树求解即可，下面用了二分，其实可以直接算出来

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 2e5 + 10;
const int H = 1e5;
const double eps = 1e-10;
int n, q, h[maxn], tot;
int root[maxn];
int ls[maxn*30], rs[maxn*30];
ll sum[maxn];struct node{ll num, sum;node operator +(const node& A)const{return{num+A.num, sum+A.sum};}node operator -(const node& A)const{return{num-A.num, sum-A.sum};}
} t[maxn*30];void update(int &rt, int pre, int pos, int l, int r){if(l>pos || r<pos) return;rt = ++tot;t[rt] = t[pre];ls[rt] = ls[pre], rs[rt] = rs[pre];if(l == r){t[rt].num++, t[rt].sum += l;return ;}int m = l + r >> 1;update(ls[rt], ls[pre], pos, l, m);update(rs[rt], rs[pre], pos, m+1, r);t[rt] = t[ls[rt]] + t[rs[rt]];
}node query(int rt, int pre, int L, int R, int l, int r){if(l>R || r<L) return{0, 0};if(L<=l && r<=R) return t[rt] - t[pre];int m = l + r >> 1;node ret1 = query(ls[rt], ls[pre], L, R, l, m);node ret2 = query(rs[rt], rs[pre], L, R, m+1, r);return ret1 + ret2;
}double check(double k, int l, int r){int p = ceil(k);double ret1 = query(root[r], root[l-1], 1, p-1, 1, H).sum;double ret2 = k * query(root[r], root[l-1], p, H, 1, H).num;
//	printf("%.6f   %.6f   %.6f\n", k, ret1, ret2);return ret1 + ret2;
}int main() {scanf("%d%d", &n, &q);for(int i=1; i<=n; i++){scanf("%d", h+i);sum[i] = sum[i-1] + h[i];update(root[i], root[i-1], h[i], 1, H);}while(q--){int l, r, x, y;scanf("%d%d%d%d", &l, &r, &x, &y);double all = 1.0 * (sum[r] - sum[l-1]);all -= all / y * x;double L = 0, R = 1e5, mid;while(L < R-eps){mid = (L + R) / 2;if(check(mid, l, r) >= all) R = mid;else L = mid;}printf("%.8f\n", R);}
}