#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
struct N{
	ll p,l;
};
vector<N> v[100010];
int lowbit(int x){
	return x&(-x);
}
struct BIT{
	ll tr[100010];
	void add(int x,ll v){
		for(int i=x;i<=1e5;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	ll find(int x){
		ll ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i];
		}
		return ans;
	}
}tr,trv;
struct Q{
	ll p,l,id;
}qq[100010],u1[100010],u2[100010];
ll ans[100010];
int get(ll v){
	int l=1,r=1e5;
	while(l<r){
		int mid=(l+r)>>1;
		if(tr.find(mid)>=v)r=mid;
		else l=mid+1;
	}
	return r;
}
ll getv(int x,ll v){
	return trv.find(x-1)+(v-tr.find(x-1))*x;
}
void solve(int l,int r,int x,int y){
	if(l==r){
		for(int i=x;i<=y;i++){
			ans[qq[i].id]=l;
		}
		return ;
	}
	int mid=(l+r+1)>>1;
	for(int i=mid;i<=r;i++){
		for(N j:v[i]){
			tr.add(j.p,j.l);
			trv.add(j.p,j.p*j.l);
		}
	}
	int n1=0,n2=0;
	for(int i=x;i<=y;i++){
		ll x=get(qq[i].l),v=getv(x,qq[i].l);
		if(tr.find(x)>=qq[i].l&&v<=qq[i].p)u2[++n2]=qq[i];
		else u1[++n1]=qq[i];
	}
	int id=x;
	for(int i=1;i<=n1;i++)qq[id++]=u1[i];
	for(int i=1;i<=n2;i++)qq[id++]=u2[i];
	solve(l,mid-1,x,x+n1-1);
	for(int i=mid;i<=r;i++){
		for(N j:v[i]){
			tr.add(j.p,-j.l);
			trv.add(j.p,-j.p*j.l);
		}
	}
	solve(mid,r,x+n1,y);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		ll d,p,l;
		cin>>d>>p>>l;
		v[d].push_back({p,l});
	}
	for(int i=1;i<=q;i++){
		cin>>qq[i].p>>qq[i].l;
		qq[i].id=i;
	}
	solve(0,1e5,1,q);
	for(int i=1;i<=q;i++){
		if(ans[i])cout<<ans[i]<<'\n';
		else cout<<"-1\n";
	}
	return 0;
}

混合果汁（P4602）

题意分析

有n种果汁，每种果汁有价格a_i和数量b_i。需要从这些果汁中选出m个（m为正整数，1≤m≤n），每种果汁最多选b_i个，求对于每个m（1≤m≤n）的最小总价格。

解题思路

采用整体二分+线段树的方法。整体二分用于处理多个查询（不同m值）的最小总价格问题；线段树用于高效维护和查询果汁的数量与价格信息，支持快速计算在某价格下可选取的果汁总数。

算法实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int INF = 1e9 + 7;

struct Juice {
    int a, b;
    bool operator<(const Juice& other) const {
        return a < other.a;
    }
} juice[MAXN];

struct Query {
    int m, idx; // m为查询的数量，idx为结果存储位置
} query[MAXN];

int n, k, ans[MAXN];
int total;

// 线段树维护每个价格区间的果汁数量和前缀和
struct SegmentTree {
    int sum[MAXN << 2], lazy[MAXN << 2];
    
    void push_up(int p, int l, int r) {
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }
    
    void push_down(int p, int l, int r) {
        if (lazy[p] && l != r) {
            int mid = (l + r) >> 1;
            sum[p << 1] += lazy[p] * (mid - l + 1);
            lazy[p << 1] += lazy[p];
            sum[p << 1 | 1] += lazy[p] * (r - mid);
            lazy[p << 1 | 1] += lazy[p];
            lazy[p] = 0;
        }
    }
    
    void build(int p, int l, int r) {
        lazy[p] = 0;
        if (l == r) {
            sum[p] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << | 1, mid + 1, r);
        sum[p] = sum[p << 1] + sum[p << 1 | 1];
    }
    
    void update(int p, int l, int r, int ql, int qr, int val) {
        if (qr < l || ql > r) return;
        if (ql <= l && r <= qr) {
            sum[p] += val * (r - l + 1);
            lazy[p] += val;
            return;
        }
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        update(p << 1, l, mid, ql, qr, val);
        update(p << 1 | 1, mid + 1, r, ql, qr, val);
        push_up(p, l, r);
        
    }
    
    int query_sum(int p, int l, int r, int ql, int qr) {
        if (qr < l || ql > r) return 0;
        if (ql <= l && r <= qr) return sum[p];
        push_down(p, l, r);
        int mid = (l + r) >> 1;
        return query_sum(p << 1, l, mid, ql, qr) + query_sum(p << 1 | 1, mid + 1, r, ql, qr);
    }
} st;

// 整体二分处理函数 [l, r]为当前二分的答案范围，queries为待处理的查询
void solve(int l, int r, int ql, int qr) {
    if (ql > qr) return; // 处理完所有查询
    if (l == r) { // 找到答案
        for (int i = ql; i <= qr; ++i) {
            ans[query[i].idx] = l;
        }
        return;
    }
    int mid = (l + r) >> 1;
    int qm = ql; // 左半部分的查询（答案 <= mid）
    int qn = qr; // 右半部分的查询（答案 > mid）
    
    // 先将所有价格 <= mid 的果汁加入线段树
    int p = 0;
    while (p < n && juice[p].a <= mid) { // 假设juice已按a排序
        st.update(1, 1, n, p + 1, p + 1, juice[p].b); // 价格为a_i，位置p+1，数量b_i
        p++;
    }
    
    // 处理每个查询，判断在mid下能否满足数量要求
    for (int i = ql; i <= qr; ++i) {
        int m = query[i].m;
        int sum = st.query_sum(1, 1, n, 1, n); // 总数量
        if (sum >= m) { // 可以满足，答案可能更小
            ans[query[i].idx] = mid;
            qm++;
        } else { // 不能满足，答案需要更大
            qn--;
        }
    }
    
    // 恢复线段树状态（移除加入的果汁）
    for (int i = p - 1; i >= 0; --i) {
        st.update(1, 1, n, i + 1, i + 1, -juice[i].b);
    }
    
    // 递归处理左右两部分
    solve(l, mid, ql, qm - 1);
    solve(mid + 1, r, qm, qr);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> juice[i].a >> juice[i].b;
    }
    sort(juice, juice + n); // 按价格排序
    
    for (int i = 0; i < k; ++i) {
        cin >> query[i].m;
        query[i].idx = i;
    }
    
    st.build(1, 1, n); // 初始化线段树
    
    int L = 0, R = 1e9; // 二分答案范围
    solve(L, R, 0, k - 1);
    
    for (int i = 0; i < k; ++i) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}

C110 整体二分+线段树 P4602 [CTSC2018] 混合果汁