混合果汁 bzoj-5343 Ctsc-2018
题目大意：给定$n$中果汁，第$i$种果汁的美味度为$d_i$，每升价格为$p_i$，每次最多添加$l_i$升。现在要求用这$n$中果汁调配出$m$杯混合果汁。第$j$杯混合果汁的要求是总价格不多余$g_j$，总体积不小于$L_j$且美味度最大。一杯混合果汁的美味度为所有添加的果汁的美味度的最小值。求$m$杯混合果汁的美味度之和的最大值。
注释：$1\le n,m,d_i,p_i,l_i\le 10^5$，$1\le g_i,L_i\le 10^{18}$。
想法：
显然每种混合果汁之间是独立的。
对于每一个询问，我们二分答案美味度。
这样的话所有比$mid$大的果汁随便选，满足询问条件。
我们判断当前的$mid$是否合法，其实就是判断一下组成$L_j$最少需要多少钱。
正确的选择肯定是选美味度大于$mid$中最便宜的，取到上限然后取第二便宜的。
这样的话我们既需要维护美味度序列，还需要保证价格递增。这是二维的，显然想到树套树。
其实如果只有两维的话主席树是完全可以胜任的。
进而我们把果汁按照美味度排序，在这个序列上以价格为权值建立主席树即可。
检验就是把主席树$mid$到后面这段权值线段树取出来。每次取最便宜的操作就相当于在权值线段树上二分即可。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; typedef long long ll;
const int N=1e5+5;
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;}
ll rd() {ll x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
ll g,L;
int n,m,md,mp,tot;
int rt[N],ls[N*20],rs[N*20];
ll s[N*20],sz[N*20],sum[N];
struct node{int p,l;};
vector<node>t[N];
void update(int &x,int l,int r,int k,int v)
{
sz[++tot]=sz[x]+v;
s[tot]=s[x]+1ll*k*v;
ls[tot]=ls[x]; rs[tot]=rs[x]; x=tot;
if(l==r)return;int mid=(l+r)>>1;
if(k<=mid) update(ls[x],l,mid,k,v);
else update(rs[x],mid+1,r,k,v);
}
ll query(int x,int l,int r,ll k)
{
if(l==r) return l*k;
int mid=(l+r)>>1;
if(k<=sz[ls[x]])return query(ls[x],l,mid,k);
return s[ls[x]]+query(rs[x],mid+1,r,k-sz[ls[x]]);
}
bool check(int mid)
{
if(sum[mid]<L)return 0;
return query(rt[mid],1,mp,L)<=g;
}
int solve()
{
int l=0,r=md,ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=n;i++)
{
int d=rd(),p=rd(),l=rd();
t[d].push_back((node){p,l});
md=max(md,d); mp=max(mp,p);
}
for(int i=md;i>=0;i--)
{
rt[i]=rt[i+1]; sum[i]=sum[i+1];
for(int j=0,k=t[i].size();j<k;j++)
{
update(rt[i],1,mp,t[i][j].p,t[i][j].l);
sum[i]+=t[i][j].l;
}
}
for(int i=1;i<=m;i++)
{
g=rd(),L=rd();
printf("%d\n",solve());
}
return 0;
}
小结：好题好题。本来是练习整体二分结果做成了主席树。