题意：

标记为\(1-n\)的竹子，\(q\)个询问，每次给出\(l,r,x,y\)。要求为砍区间\(l,r\)的柱子，要求砍\(y\)次把所有竹子砍完，每次砍的时候选一个高度，把比他高的都砍下来，并且这\(y\)次砍下来长度都相等，问第\(x\)次砍在什么高度。

思路：

显然就是要求选一个高度砍，使得剩下的高度为\((sum[r] - sum[l - 1]) - (sum[r] - sum[l - 1])/y * x\)，那么直接建好主席树，然后二分出这个高度。

主席树好啊。

代码：

#include<map>

#include<set>

#include<queue>

#include<cmath>

#include<stack>

#include<ctime>

#include<string>

#include<vector>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

const int maxn = 2e5 + 5;

const int MAXM = 20000000 + 5;

const int INF = 0x3f3f3f3f;

const ull seed = 131;

const ll MOD = 1e9 + 7;

using namespace std;

int root[maxn], tot;

vector<ll> vv;

int getId(int x){

    return lower_bound(vv.begin(), vv.end(), x) - vv.begin() + 1;

}

struct node{

    int lson, rson;

    int num;

    ll sum;

}T[maxn * 40];

void update(int l, int r, int &now, int pre, int v, int pos){

    T[++tot] = T[pre], T[tot].num += v, T[tot].sum += v * vv[pos - 1], now = tot;

    if(l == r) return;

    int m = (l + r) >> 1;

    if(m >= pos)

        update(l, m, T[now].lson, T[pre].lson, v, pos);

    else

        update(m + 1, r, T[now].rson, T[pre].rson, v, pos);

}

ll query(int l, int r, int now, int pre, double k){

    if(l == r){

        if(vv[l - 1] < k) return T[now].sum - T[pre].sum;

        return 0;

    }

    int m = (l + r) >> 1;

    if(vv[r - 1] < k) return T[now].sum - T[pre].sum;

    if(vv[m - 1] < k)

        return T[T[now].lson].sum - T[T[pre].lson].sum + query(m + 1, r, T[now].rson, T[pre].rson, k);

    else

        return query(l, m, T[now].lson, T[pre].lson, k);

}

ll querynum(int l, int r, int now, int pre, double k){

    if(l == r){

        if(vv[l - 1] < k) return T[now].num - T[pre].num;

        return 0;

    }

    int m = (l + r) >> 1;

    if(vv[r - 1] < k) return T[now].num - T[pre].num;

    if(vv[m - 1] < k)

        return T[T[now].lson].num - T[T[pre].lson].num + querynum(m + 1, r, T[now].rson, T[pre].rson, k);

    else

        return querynum(l, m, T[now].lson, T[pre].lson, k);

}

ll h[maxn], psum[maxn];

int main(){

    int n, Q;

    vv.clear();

    tot = 0;

    T[0].lson = T[0].rson = T[0].num = T[0].sum = 0;

    scanf("%d%d", &n, &Q);

    psum[0] = 0;

    for(int i = 1; i <= n; i++){

        scanf("%lld", &h[i]);

        vv.push_back(h[i]);

        psum[i] = psum[i - 1] + h[i];

    }

    sort(vv.begin(), vv.end());

    vv.erase(unique(vv.begin(), vv.end()), vv.end());

    for(int i = 1; i <= n; i++){

        update(1, vv.size(), root[i], root[i - 1], 1, getId(h[i]));

    }

    while(Q--){

        int l, r, x, y;

        scanf("%d%d%d%d", &l, &r, &x, &y);

        double per = (psum[r] - psum[l - 1]) * 1.0 / y;

        double f = (psum[r] - psum[l - 1]) * 1.0 - per * x;

        double L = 0, R = f + 10, m, ans;

        while(R - L > 1e-7){

            m = (L + R) / 2.0;

            double small = query(1, vv.size(), root[r], root[l - 1], m);

            int num = querynum(1, vv.size(), root[r], root[l - 1], m);

            double now = small + (r - l + 1 - num) * 1.0 * m;

            if(now >= f){

                ans = m;

                R = m;

            }

            else L = m;

        }

        printf("%.8f\n", ans);

    }

    return 0;

}

巴特西

牛客多校第九场H Cutting Bamboos（主席树区间比k小的个数）题解

题意：

思路：

代码：

最新文章

热门文章

巴特西

牛客多校第九场H Cutting Bamboos（主席树 区间比k小的个数）题解

题意：

思路：

代码：

最新文章

热门文章

牛客多校第九场H Cutting Bamboos（主席树区间比k小的个数）题解