Solved:3
Rank:181
H Cutting Bamboos
这个东西好像叫整体二分
#include <bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; int n, m, cnt, len; int a[MAXN]; int b[MAXN]; int t[MAXN]; int num[MAXN << 5]; int ls[MAXN << 5]; int rs[MAXN << 5]; double sum[MAXN << 5]; int build(int l, int r) { int rt = ++cnt; sum[0] = 0, num[0] = 0; int mid = l + r >> 1; if(l < r) { ls[rt] = build(l, mid); rs[rt] = build(mid + 1, r); } return rt; } int add(int o, int l, int r, int k, int v) { int rt = ++cnt; ls[rt] = ls[o]; rs[rt] = rs[o]; sum[rt] = sum[o] + 1.0 * v; num[rt] = num[o] + 1; int mid = l + r >> 1; if(l < r) if(k <= mid) ls[rt] = add(ls[o], l, mid, k, v); else rs[rt] = add(rs[o], mid + 1, r, k, v); return rt; } double query(int ql, int qr, int l, int r, double k, int tot) { if(l == r) return k / (1.0 * (num[qr] - num[ql] + tot)); int mid = l + r >> 1; double lsum = sum[ls[qr]] - sum[ls[ql]]; double rsum = 1.0 * mid * (num[rs[qr]] - num[rs[ql]] + tot); if(lsum + rsum > k) return query(ls[ql], ls[qr], l, mid, k, tot + num[rs[qr]] - num[rs[ql]]); else return query(rs[ql], rs[qr], mid + 1, r, k - lsum, tot); } int main() { cnt = 0; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); len = unique(b + 1, b + 1 + n) - b - 1; t[0] = build(0, 100000); for(int i = 1; i <= n; i++) t[i] = add(t[i - 1], 0, 100000, a[i], a[i]); while(m--) { int l, r, x, y; scanf("%d%d%d%d", &l, &r, &x, &y); double tmp = 1.0 * (sum[t[r]] - sum[t[l - 1]]) / (1.0 * y); printf("%.8lf ", query(t[l - 1], t[r], 0, 100000, tmp * (y - x), 0)); } return 0; }