我看到题解里面大多是将果汁排序后，按照果汁的下标建立主席树。我用这个做法也可以ac。

但是我尝试了另一种写法，是按照美味程度建立主席树。root[i] 是美味程度为 $i$ 的果汁线段树的树根。根据美味程度从大到小遍历果汁：

• 如果没有美味程度为 $i$ 的果汁，那么 root[i] = root[i+1]；
• 如果第一次出现美味程度为 $i$ 的果汁，那么在 root[i + 1] 的基础上新开一条链，加入这个果汁的影响；
• 如果上一个果汁的美味程度也是 $i$，那么就在 root[i] 上面原地修改

因为美味程度的范围和果汁数量一样都是 $[1,10^5]$，所以理论上似乎复杂度没问题。但是只过了前面几个点，后面全部 tle。想请教一下原因。

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int, int>
#define endl "\n"
/**********************  Core code begins  **********************/

// 可持久化权值线段树，维护的桶下标是果汁单价，内容是总量和总价格
struct segtr {
	struct Info {
		int l, r, vol, sum; // 左儿子，右儿子，总容量，总价格
	};
	vector<Info> info;
	int cnt = 0;
	segtr(int n): info(n * 64) {}
	// 插入一个果汁，并新增一个版本的链，单价 x，体积 k，
	int insert(int p, int l, int r, int x, int k) {
		int rt = ++cnt;
		info[rt] = info[p];
		info[rt].vol += k;
		info[rt].sum += x * k;
		if (l == r) {
			return rt;
		}
		int mid = (l + r) >> 1;
		if (x <= mid) {
			info[rt].l = insert(info[p].l, l, mid, x, k);
		} else {
			info[rt].r = insert(info[p].r, mid + 1, r, x, k);
		}
		return rt;
	}
	// 插入一个果汁，在原树上修改，单价 x，体积 k
	void modify(int p, int l, int r, int x, int k) {
		info[p].vol += k;
		info[p].sum += x * k;
		int mid = (l + r) >> 1;
		if (x <= mid) {
			modify(info[p].l, l, mid, x, k);
		} else {
			modify(info[p].r, mid + 1, r, x, k);
		}
	}
	// 在以 p 位根的线段树上查询最小的位置 pos，满足 [1, pos] 范围内的果汁容量不小于 x
	// 返回满足容量下界的果汁总价格
	int query(int p, int l, int r, int x) {
		if (info[p].vol < x) {
			return 1e18;
		}
		if (l == r) {
			return l * x;
		}
		int mid = (l + r) >> 1;
		int lp = info[p].l, rp = info[p].r;
		if (info[lp].vol >= x) {
			return query(lp, l, mid, x);
		} else {
			return info[lp].sum + query(rp, mid + 1, r, x - info[lp].vol);
		}
	}
};

void SolveTest() {
	int n, m;
	cin >> n >> m;
	struct Juice {
		int d, p, l; // 美味度，每升价格，总量
	};
	vector<Juice> juice(n + 1); 
	for (int i = 1; i <= n; i++) {
		cin >> juice[i].d >> juice[i].p >> juice[i].l;
	}
	const int N = 1e5 + 7; 	// 美味度，每升价格的上限
	vector<int> root(N + 1);
	sort(juice.begin() + 1, juice.end(), [](auto x, auto y) {
		return x.d > y.d;
	});

	segtr tr(N);
	int nowd = N;
	for (int i = 1; i <= n; i++) {
		auto [d, p, l] = juice[i];
		if (d < nowd) {
			while (--nowd > d) {
				root[nowd] = root[nowd + 1];
			}
			root[nowd] = tr.insert(root[nowd + 1], 1, N, p, l);
		} else {
			tr.modify(root[nowd], 1, N, p, l);
		}
	}
	while (nowd) {	// 这里不要忘，否则二分答案的时候会出问题
		--nowd;
		root[nowd] = root[nowd + 1];
	}

	while (m--) {
		int x, y;		// 体积不少于 x，价格不超过 y
		cin >> y >> x;

		auto check = [&](int ans)->bool {
			return tr.query(root[ans], 1, N, x) <= y;
		};	

		int lo = 0, hi = N;
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;	

			if (check(mid)) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		if (lo == 0) {
			lo = -1;
		}
		cout << lo << endl;
	}
}

/**********************  Core code ends  ***********************/
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	// cin >> T;
	for (int i = 1; i <= T; i++) {
		SolveTest();
	}
	return 0;
}