牛客竞赛第九场 H Cutting Bamboos 主席树 + 二分

发表于 分类于 阅读次数：

一道主席树的好题，虽然WA到哭， 但是最后再自己静下心来理一遍思路，还是很多地方值得学习的。

链接

思路

根据题意我们可以很快算出X次Cut后，树木应该剩余的总的高度，但是我们不知道第X次应该从哪个高度去Cut，因此可以二分枚举这个高度，我们把序列用主席树建好，然后就可以查询小于当前高度的总的高度了，再加上高于当前高度的树木的个数 * 当前高度 就是 总的剩余的高度了，我们把这个和理论值比较即可二分。注意Long long 和double的问题。另外本题不需要离散化，因为最大的高度才100000，因此我们可以直接根据高度值建树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-10;
const int MAXN = 200005;
struct node{
   int l,r;
   ll sum, num;
}tr[MAXN * 40];
int rt[MAXN],h[MAXN],tot;
ll sum_pre[MAXN];             //注意Longlong
void build(int &o, int l, int r)
{
    o = ++tot;
    tr[o].num = 0, tr[o].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tr[o].l, l, mid);
    build(tr[o].r, mid + 1, r);
}

void update(int &o, int last, int l, int r, int pos)
{
    o = ++tot;
    tr[o].l = tr[last].l;
    tr[o].r = tr[last].r;
    tr[o].num = tr[last].num + 1;
    tr[o].sum = tr[last].sum + pos;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(pos <= mid ) update(tr[o].l, tr[last].l, l, mid, pos);
    else update(tr[o].r, tr[last].r,mid + 1, r, pos);
}
ll sum, num;

void query(int &o, int last, int l, int r, int k)      //查询小于等于K的树木的高度的总和
{
    if(k < l) return;
    if(k >= r)
    {
        sum += tr[o].sum - tr[last].sum;
        num += tr[o].num - tr[last].num;
        return;
    }
    int mid = (l + r) >> 1;
    query(tr[o].l, tr[last].l, l, mid, k);
    query(tr[o].r, tr[last].r, mid + 1, r, k);
}
int main()
{
    int n, m;
    scanf("%d%d",&n,&m);
    build(rt[0], 1, 100000);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&h[i]);
        update(rt[i], rt[i - 1], 1, 100000, h[i]);
        sum_pre[i] = sum_pre[i - 1] + h[i];
    }
    while(m--)
    {
        int L, R, x, y;
        scanf("%d%d%d%d",&L,&R,&x,&y);
        double zong = sum_pre[R] - sum_pre[L - 1];
        double standard = zong - (zong * 1.0 )/y * x;
        double l = 0, r = 100000;
        while(r - l > eps)
        {
            double mid = (l + r) / 2;
            sum = 0, num = 0;
            query(rt[R], rt[L - 1], 1, 100000, (int)mid);
            double num1 = (sum + (R - L + 1 - num) * mid);
            if(num1 > standard)
                r = mid;
            else l = mid;
        }
        printf("%.15f\n", l);
    }
}