#include"lottery.h" #include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5; int A[MAXN],pos[MAXN],va[MAXN],vb[MAXN],V[MAXN],seg[MAXN*4],lg,N; int getlog(long long n) { return 63-__builtin_clzll(n); } bool comp(int a,int b) { return A[a]<A[b]; } struct node { vector<long long> pref; vector<int> idx; void build(int l,int r) { for(int i=l;i<=r;i++) idx.push_back(pos[i]); sort(idx.begin(),idx.end()); long long sum=0; for(auto v:idx) pref.push_back(sum+=A[v]); } pair<long long,int> get(int l,int r) { r=upper_bound(idx.begin(),idx.end(),r)-idx.begin()-1; l=lower_bound(idx.begin(),idx.end(),l)-idx.begin()-1; if(l<0) return {pref[r],r+1}; return {pref[r]-pref[l],r-l}; } }; node fa[MAXN],fb[MAXN]; void build(int l,int r,int pos) { if(l==r) { seg[pos]=V[l]; return ; } int mid=(l+r)/2; build(l,mid,pos*2); build(mid+1,r,pos*2+1); seg[pos]=min(seg[pos*2],seg[pos*2+1]); } int get(int l,int r,int u,int v,int pos) { if(u<=l&&r<=v) return seg[pos]; int mid=(l+r)/2; if(v<=mid) return get(l,mid,u,v,pos*2); if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1); return min(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1)); } void init(int n,int q,vector<int> X,vector<int> Y) { lg=getlog(n),N=n; for(int i=1;i<=n;i++) A[i]=X[i-1],pos[i]=i; sort(pos+1,pos+n+1,comp); for(int i=1;i<=n;i++) va[i]=A[pos[i]],fa[i].build(i-(i&-i)+1,i); for(int i=1;i<=n;i++) A[i]=Y[i-1],pos[i]=i; sort(pos+1,pos+n+1,comp); for(int i=1;i<=n;i++) vb[i]=A[pos[i]],fb[i].build(i-(i&-i)+1,i); for(int i=1;i<=n;i++) V[i]=X[i-1]+Y[i-1]; build(1,n,1); } int max_prize(int l,int r) { l++,r++; int pa=0,pb=0,lena=-(r-l+1)/2,lenb=-(r-l+1)/2; long long suma=0,sumb=0; for(int i=lg;i+1;i--) { if(pa+(1<<i)<=N) { pair<long long,int> res=fa[pa+(1<<i)].get(l,r); if(suma+res.first>=va[pa+(1<<i)]*(lena+res.second)) pa+=(1<<i),suma+=res.first,lena+=res.second; } if(pb+(1<<i)<=N) { pair<long long,int> res=fb[pb+(1<<i)].get(l,r); if(sumb+res.first>=vb[pb+(1<<i)]*(lenb+res.second)) pb+=(1<<i),sumb+=res.first,lenb+=res.second; } } return min(get(1,N,l,r,1),(int)min(suma/lena,sumb/lenb)); }