题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6609
大致题意是求出每个位置i最小需要将几个位置j变为0(j<i)，使得$\sum_{j=1}^{i}a[j]<=m$
可以将题意换一下，删除最少的个数=i-1-保留最多的个数。
则建权值线段树，同时维护个数与权值。题目转化为用最多的权值线段树中的数凑出m-a[i]这个数。
所以就从小到大取数即可。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#define lson l, mid, i<<1
#define rson mid + 1, r, i<<1|1
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
ll val[maxn * ];
int num[maxn * ];
int a[maxn], b[maxn];
void up(int i) {
val[i] = val[i << ] + val[i << | ];
num[i] = num[i << ] + num[i << | ];
}
void build(int l, int r, int i) {
val[i] = num[i] = ;
if (l == r)
return;
int mid = l + r >> ;
build(lson);
build(rson);
}
int query(int pos, int l, int r, int i) {
if (val[i] <= pos)
return num[i];
if (l == r)
return min(num[i], pos / b[l]);//比较该数的个数和需要多少个数
int mid = l + r >> ;
if (val[i << ] >= pos)
return query(pos, lson);
else
return num[i << ] + query(pos - val[i << ], rson);
}
void update(int pos, int l, int r, int i) {
if (l == r) {
val[i] += b[pos];
num[i]++;
return;
}
int mid = l + r >> ;
if (pos <= mid)update(pos, lson);
else update(pos, rson);
up(i);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= n; i++)
scanf("%d", &a[i]), b[i] = a[i];
sort(b + , b + + n);
int k = unique(b + , b + + n) - b - ;
build(, k, );
for (int i = ; i <= n; i++) {
if (i == )
printf("0 ");
else
printf("%d%c", i - - query(m - a[i], , k, ), i == n ? '\n' : ' ');
int pos = lower_bound(b + , b + + k, a[i]) - b;
update(pos, , k, );
}
}
}