题目

// ZZQF5677 | 20231018 | T2 （权值线段树 v7.0 代） 
// 线段树 + 动态开点。 
#include <bits/stdc++.h>
using namespace std;
long long T, n, M, a[1000005];
struct TREE {
	long long l, r; // 管辖的区间。
	long long con; // 数字个数。（可以用来查询第 k 大） 
	long long sum; // 求和（体积）。 
	long long lson, rson; // 左子结点和右子节点。 
} tree[2000005];
long long tcnt = 1;
void build(long long l, long long r, long long root) {
	tree[root].l = l;
	tree[root].r = r;
	if (tree[root].lson == 0) {
		tcnt++;
		tree[root].lson = tcnt;
	}
	if (tree[root].rson == 0) {
		tcnt++;
		tree[root].rson = tcnt;
	}
	return ;
}
void update(long long l/*管辖的区间*/, long long r/*管辖的区间*/, long long root, long long k/*插入了某个数字*/) {
	build(l, r, root);
	//tree[root].lson = root * 2;
	//tree[root].rson = root * 2 + 1;
	//cout << root << "\n";
	if (l == r) {
	  tree[root].con++;
		tree[root].sum = tree[root].con * k;
		//cout << tree[root].con << "===\n";
		return ;
	}
	long long mid = (l + r) / 2;
	if (k <= mid) { // Important!!!
		update(l, mid, tree[root].lson, k);
	} else {
		update(mid + 1, r, tree[root].rson, k);
	}
	tree[root].sum = tree[tree[root].lson].sum + tree[tree[root].rson].sum;
	tree[root].con = tree[tree[root].lson].con + tree[tree[root].rson].con;
	return ;
}
long long getsum(long long l/*查询左区间*/, long long r/*查询右区间*/, long long root) { // 查询体积为 l 到 r 的人的总共体积为多少。 
	if (l <= tree[root].l && tree[root].r <= r) {
		return tree[root].sum;
	}
	long long mid = (tree[root].l + tree[root].r) / 2;
	long long sum = 0;
	if (l <= mid && tree[root].lson != 0) {
		sum += getsum(l, r, tree[root].lson);
	}
	if (mid + 1 <= r && tree[root].rson != 0) {
		sum += getsum(l, r, tree[root].rson);
	}
	return sum;
}
long long getcon(long long l/*查询左区间*/, long long r/*查询右区间*/, long long root) { // 查询体积为 l 到 r 的人的总共体积为多少。 
	if (l <= tree[root].l && tree[root].r <= r) {
		return tree[root].con;
	}
	long long mid = (tree[root].l + tree[root].r) / 2;
	long long con = 0;
	if (l <= mid && tree[root].lson != 0) {
		con += getcon(l, r, tree[root].lson);
	}
	if (mid + 1 <= r && tree[root].rson != 0) {
		con += getcon(l, r, tree[root].rson);
	}
	return con;
}
long long getk(long long root, long long k) { // 获取前 k 个人的体积。
	if (tree[root].con > k && tree[tree[root].lson].con == 0 && tree[tree[root].rson].con == 0 /*没有儿子即它是叶子结点*/) {
		//cout << tree[root].sum << "信息学怎么你了？\n";
		return k * tree[root].l; 		
	} 
	if (tree[root].con <= k) {
		return tree[root].sum;
	}
	long long tj = 0;
	//cout << tree[root].sum << "===\n";
	if (k <= tree[tree[root].lson].con) {
		tj += getk(tree[root].lson, k);
	} else {
		k -= tree[tree[root].lson].con;
		tj += tree[tree[root].lson].sum;
		tj += getk(tree[root].rson, k);
	}
	return tj;
}
long long getT(long long root, long long tj) { // 查询（1-?）当一共体积为 tj 时一共有多少个人（车能装下多少个人，即这些人的总和小于等于车的容积。）。 
	//cout << tree[root].r << "\n";
	//cout << tj << "\n";
	if (tree[root].sum <= tj) {
		return tree[root].con;
	}
	if (tree[root].sum > tj && tree[tree[root].lson].con == 0 && tree[tree[root].rson].con == 0 /*没有儿子即它是叶子结点*/) {
		//cout << tree[root].sum << "信息学怎么你了？\n";
		return tj / (tree[root].l); 		
	} 
	//long long mid = (tree[root].l + tree[root].r) / 2;
	if (tj <= tree[tree[root].lson].sum) {
		//cout << "-=-=-=-\n";
		return getT(tree[root].lson, tj);
	} else {
		long long con = 0;
		//cout << tj << " " << tree[tree[root].rson].sum << "----\n";
		tj -= tree[tree[root].lson].sum;
		con += tree[tree[root].lson].con;
		con += getT(tree[root].rson, tj);
		return con;
	}
	return 0;
}
void Segment_Tree_Clear() {
	for (long long i = 0; i <= 200002; i++) {
		tree[i] = (TREE){0, 0, 0, 0, 0, 0};
	}
	return ;
}
int main() {
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while (T--) {
		//cout << "\n===============================================================\n";
		Segment_Tree_Clear();
		cin >> n >> M;
		tcnt = 1;
		long long maxx = -1; 
		for (long long i = 1; i <= n; i++) {
			cin >> a[i];
			maxx = max(maxx, a[i]);
			//update(1, 1000000000, 1, a[i]);
		}
		
		for (long long i = 1; i <= n; i++) {
			/* 方案一：二分前 k 个人的体积，查找一个 k 满足它们的体积小于等于容积。 
			long long l = 0, r = i - 1, mid = (l + r) / 2; 
			while (l <= r) {
				mid = (l + r) / 2;
				if (getk(1, mid) > M - a[i]) {
					//cout << getk(1, mid) << "\n";
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			cout << i - (l - 1 + 1) << " ";
			update(1, maxx + 5, 1, a[i]);
			*/
			cout << i - (getT(1, M - a[i]) + 1) << " ";
			update(1, maxx + 5, 1, a[i]);
		}
		//cout << getT(1, 100) << " ";
		cout << "\n";
		//cout << g;etk(1, 4) << "\n";
		//cout << getsum(39, 61, 1) << "\n";
		//cout << getcon(60, 80, 1) << "\n";
		//cout << tree[1].sum << "\n";
		
	}
	//cout << tree[1].lson << " " << tree[124].r << "\n";
	return 0;
}

谢谢（)