LibreOJ 2555 「CTSC2018」混合果汁

首先答案显然可以二分。
于是问题变成给定 mid，求所有美味度不小于 mid 的果汁种类中混合出至少 Li 升的最小总价格。
其实是个人都能看出来这个地方的至少是没用的，最优解肯定是恰好这么多……

如果只看不小于 mid 的果汁种类，可以以每一种果汁的单价建一棵权值线段树，每个结点保存总体积与总价。
于是直接权值线段树上二分即可求得最小总价格。
实际上用了两个二分，于是复杂度是 O(log2n) 的。

然鹅我们还要多组询问，与其离线整体二分，不如直接把线段树可持久化了。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5;
int n,m;
struct note
{
    int d,p,l;
} a[N + 5];
vector<int> p[N + 5];
struct node
{
    long long cnt,sum;
    int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int k,int &p,int tl,int tr)
{
    static int tot = 0;
    seg[++tot] = seg[p],seg[p = tot].cnt += k,seg[p].sum += (long long)x * k;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,k,seg[p].ls,tl,mid) : insert(x,k,seg[p].rs,mid + 1,tr);
}
long long query(int p,int tl,int tr,long long L)
{
    if(!p || tl == tr)
        return L * tl;
    int mid = tl + tr >> 1;
    return L <= seg[seg[p].ls].cnt ? query(seg[p].ls,tl,mid,L) : seg[seg[p].ls].sum + query(seg[p].rs,mid + 1,tr,L - seg[seg[p].ls].cnt);
}
inline int query(long long g,long long L)
{
    int l = 1,r = N,mid,ret = -1;
    while(l <= r)
    {
        mid = l + r >> 1;
        L <= seg[rt[mid]].cnt && query(rt[mid],1,N,L) <= g ? (ret = mid,l = mid + 1) : r = mid - 1;
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d",&a[i].d,&a[i].p,&a[i].l),p[a[i].d].push_back(i);
    for(register int i = N;i && (rt[i] = rt[i + 1],1);--i)
        for(register int j = 0;j < p[i].size();++j)
            insert(a[p[i][j]].p,a[p[i][j]].l,rt[i],1,N);
    long long g,L;
    for(;m;--m)
        scanf("%lld%lld",&g,&L),printf("%d\n",query(g,L));
}