https://ac.nowcoder.com/acm/contest/889#question
题意
n个竹子排成一排，每次选一个高度切竹子，每次切下的总长度必须相等。
q次查询，每次查询一个区间[l,r]，x，y，表示在这个区间里切竹子，
要保证一共切y次切完，问第x次切竹子的高度。
题解
一共要切掉的总长度为区间总长度len=x*S/y。
对高度建主席树，二分一个整数高度h，使得高度>=h的竹子的总贡献<=len，
然后把剩下的小数部分计算出来。
代码很好写
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 #define pa pair<int,ll> 6 using namespace std; 7 #define ll long long 8 #define mk make_pair 9 #define pb push_back 10 #define se second 11 #define fi first 12 ll mod=998244353; 13 const int N=2e5+5; 14 int n,q; 15 int cnt; 16 int sum[N*22],ls[N*22],rs[N*22],rt[N]; 17 ll val[N*22]; 18 void up(int &o,int pre,int l,int r,int p){ 19 o=++cnt; 20 val[o]=val[pre]+p; 21 sum[o]=sum[pre]+1; 22 ls[o]=ls[pre]; 23 rs[o]=rs[pre]; 24 if(l==r)return; 25 int m=(l+r)/2; 26 if(p<=m)up(ls[o],ls[pre],l,m,p); 27 else up(rs[o],rs[pre],m+1,r,p); 28 } 29 ll cal(int o,int p){ 30 return val[o]-1ll*sum[o]*p; 31 } 32 ll qu(int o,int pre,int l,int r,int p){ 33 int m=(l+r)/2; 34 if(p<=l)return cal(o,p)-cal(pre,p); 35 ll res=qu(rs[o],rs[pre],m+1,r,p); 36 if(p<=m)res+=qu(ls[o],ls[pre],l,m,p); 37 return res; 38 } 39 int qu1(int o,int pre,int l,int r,int p){ 40 if(p<=l)return sum[o]-sum[pre]; 41 int m=(l+r)/2; 42 int res=qu1(rs[o],rs[pre],m+1,r,p); 43 if(p<=m)res+=qu1(ls[o],ls[pre],l,m,p); 44 return res; 45 } 46 int main(){ 47 scanf("%d%d",&n,&q); 48 int h=1e5; 49 for(int i=1;i<=n;i++){ 50 int x; 51 scanf("%d",&x); 52 up(rt[i],rt[i-1],1,h,x); 53 } 54 while(q--){ 55 int ql,qr,x,y; 56 cnt=0; 57 scanf("%d%d%d%d",&ql,&qr,&x,&y); 58 ll S=val[rt[qr]]-val[rt[ql-1]]; 59 int l=0,r=h; 60 while(l<r){ 61 int m=(l+r)/2; 62 ll res=qu(rt[qr],rt[ql-1],1,h,m); 63 if(1.0*res/x<1.0*S/y)r=m; 64 else l=m+1; 65 } 66 ll res=qu(rt[qr],rt[ql-1],1,h,l); 67 double g=1.0*x/y*S-res; 68 int res1=qu1(rt[qr],rt[ql-1],1,h,l); 69 g/=res1; 70 printf("%.10lf ",l-g); 71 } 72 }