2019牛客多校第⑨场H Cutting Bamboos(主席树+二分)

原题：https://ac.nowcoder.com/acm/contest/889/H

题意：

给你一些竹子，q个询问，问你从第l到第r个竹子，如果你要用y次砍完它，并且每次砍下来的长度是相同的，问你第x次砍在哪。

思路：

先求前缀和，(l,r)区间要砍y刀，每刀总长度step=(sum[r]-sum[l-1])/y，第x次砍完必定还剩下总长度为step*(y-x)的竹子。想到可以二分砍的高度，判断砍得偏高还是偏低，可以通过计算剩下得总长度比要求大还是小。设高度为h，则剩下的总长度=\(高度小于h的竹子的高度和+高度大于h的竹子数量 * x\) ，主席树可以维护区间上小于x的元素个数以及元素和，正好满足要求。

//memeory:6.7e7

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn=2e5+5;

const int N=2e5+2;

const int Log=40;

ll val[maxn*Log],sum[maxn];

int root[maxn],a[maxn],num[maxn*Log],lson[maxn*Log],rson[maxn*Log];

int tot;

double Sum,Num;

int build(int l,int r){

    int root=++tot;

    val[root]=0;

    num[root]=0;

    if(l<r){

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

        lson[root]=build(l,mid);

        rson[root]=build(mid+1,r);

    }

    return root;

}

int update(int pre,int l,int r,int x){

    int root=++tot;

    num[root]=num[pre]+1;

    val[root]=val[pre]+x;

    lson[root]=lson[pre];

    rson[root]=rson[pre];

    if(l<r){

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

        if(x<=mid) lson[root]=update(lson[pre],l,mid,x);

        else rson[root]=update(rson[pre],mid+1,r,x);

    }

    return root;

}

void query(int Old,int New,int l,int r,int k){//查区间内<=k的数的个数

	if(l>k)return;

    if(r<=k){

    	Sum+=val[New]-val[Old];

    	Num+=num[New]-num[Old];

    	return;

    }

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

    query(lson[Old],lson[New],l,mid,k);//函数开始会判断跳出，这里不需要判断

    query(rson[Old],rson[New],mid+1,r,k);

}

int main(){

    int n,q;

    cin>>n>>q;

    root[0]=build(1,n);

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

    	scanf("%d",&a[i]);

    	sum[i]=sum[i-1]+a[i];

    	root[i]=update(root[i-1],1,n,a[i]);

    }

    while(q--){

    	int l,r,x,y;

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

    	double li=0,ri=100000,eps=1e-10;

    	double step=1.0*(sum[r]-sum[l-1])/y;

    	while(ri-li>eps){

    		double mid=(li+ri)/2;

    		Sum=0;Num=0;

    		query(root[l-1],root[r],1,n,(int)mid);

    		Num=(r-l+1)-Num;//比mid矮的数量转化为比mid高的数量

    		double temp=mid*Num+Sum;

    		if(step*(y-x)<temp)//砍高了

				ri=mid;

			else li=mid;

    	}

    	printf("%.15lf\n",li);

    }

}

巴特西

2019牛客多校第⑨场H Cutting Bamboos(主席树+二分)

题意：

思路：

最新文章

热门文章