题解 | Cutting Bamboos-2019牛客暑期多校训练营第九场H题

题目来源于牛客竞赛：https://ac.nowcoder.com/acm/contest/discuss
题目描述：

输入描述：

输出描述：

示例1：


题解：

代码：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>using namespace std;
using namespace __gnu_pbds;#define fi first
#define se second
#define mp make_pair
#define pb push_backtypedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;const int N = 201111;
ll a[N+11];
const ld eps = 1e-7;struct Fenwick
{vector<ll> t;Fenwick(int n){t.assign(n+1,0);}void reset(int n){t.assign(n+1, 0);}void update(int p, ll v){p++;for (; p < (int)t.size(); p += (p&(-p))) t[p] += v;}ll query(int r) //finds [1, r] sum{                   r++;ll sum = 0;for (; r; r -= (r&(-r))) sum += t[r];return sum;}ll query(int l, int r) //finds [l, r] sum{if(l == 0) return query(r);return query(r) - query(l-1);}
};const int Q = 202222;
ld ans[Q+3];
ll pref[N+3];ll getsum(int l, int r)
{if(l==0) return pref[r];else return pref[r]-pref[l-1];
}pair<ii,ld> queries[Q+3];int main()
{ios_base::sync_with_stdio(0); cin.tie(0);int n,q; cin>>n>>q;ll mx=0;vector<ii> vec;for(int i=0;i<n;i++){cin>>a[i];pref[i]=a[i];vec.pb(mp(a[i],i));mx=max(mx,a[i]);if(i>0) pref[i]+=pref[i-1];}sort(vec.begin(),vec.end());queue<pair<pair<ld,ld>,vi> > Q;for(int z=0;z<q;z++){int l,r,x,y; cin>>l>>r>>x>>y;l--; r--;x=y-x;ld threshold = (ld(x)/ld(y))*ld(getsum(l,r));queries[z]=mp(mp(l,r),threshold);}vi all;for(int i=0;i<n;i++) all.pb(i);Q.push(mp(mp(0,mx),all));ld pre = -1;int ptr=0;Fenwick fen(n+2);Fenwick fen2(n+2);while(!Q.empty()){ld lo=Q.front().fi.fi; ld hi=Q.front().fi.se;ld mid=(lo+hi)*0.5;if(mid<pre){ptr=0; pre=-1; fen.reset(n+2); fen2.reset(n+2);}while(ptr<n&&vec[ptr].fi<=mid){fen.update(vec[ptr].se,vec[ptr].fi);fen2.update(vec[ptr].se,1);ptr++;}vi L,R;for(int v:Q.front().se){ans[v]=mid;int l=queries[v].fi.fi; int r=queries[v].fi.se; ld threshold = queries[v].se;ld sum = 0;sum+=(r-l+1-fen2.query(l,r))*ld(mid);sum+=ld(fen.query(l,r));if(sum<=threshold){R.pb(v);}else{L.pb(v);}}Q.pop();if(hi-lo>=eps){if(!L.empty()) Q.push(mp(mp(lo,mid),L));if(!R.empty()) Q.push(mp(mp(mid,hi),R));}pre=mid;}for(int i=0;i<q;i++){cout<<fixed<<setprecision(15)<<ans[i]<<'\n';}
}

更多问题，更详细题解可关注牛客竞赛区，一个刷题、比赛、分享的社区。
传送门：https://ac.nowcoder.com/acm/contest/discuss