\(\text{Links}\)
题意
有一个容量为 \(m\) \((m\le 10^9)\) 的容器和 \(n\) \((n\le 10^5)\) 个物品，第 \(i\) 个物品的体积为 \(a_i\) \((a_i\le m)\)。对于每个 \(i\) \((1\le i\le n)\) 需要求解：在必须装第 \(i\) 个物品以及装入的物品的总体积不超过 \(m\) 的情况下，你可以在前 \(i-1\) 个物品中选若干个装进去，问最少能使得前 \(i-1\) 个物品中有多少个没有被装入。
题解
物品没有除了体积之外的任何属性，所以显然贪心地装小的。
考虑 set 暴力，每次遍历前 \(i-1\) 个，一直选取最小的装进去，直到装不下就 break，然后输出答案，并插入 \(a_i\)。
时间复杂度大致是 \(O(n^2)\)，G。
但是我赛时写这个乱搞直接就过了…，这数据也是真挺厉害的。
得优化，考虑是哪些被重复做了很多次的操作造成了影响，显然是我们每次只插入一个数，但我们每次都从头开始取，记录体积总和这个过程很浪费时间。
体现出“有序”，高效维护“前缀和”。没错，树状数组。
那么我们每次在树状数组上 \(a_i\) 的位置插入 \(a_i\)，维护前缀和。查询就二分出最后一个使得前缀和 \(\le m-a_i\) 的位置，然后答案是在这个位置及其以前的数的数量，这个数量应该可以搞个 \(pos\) 映射啥的来做，但是我懒，所以直接另开了一个树状数组搞了一下。
因为 \(vmax\) 范围是 \(10^9\)，所以考虑“离散化”一下，记录一个 \(b\) 数组，表示排序之后每个数在哪个位置，如果有重复的数就按照原序列的下标依次顺延（这样子正确性显然）。
然后就做完了。
这题我赛时没切掉啊，悲。
赛后是 \(\text{rk1}\) 大神教我的。感觉这个做法还是比较巧妙的，至少肯定有我能学习的地方，膜拜。
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=100100;
int t,n,m,a[N],b[N],c1[N],c2[N];
unordered_map<int,int>vis;
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
il int lowbit(int x){
return x&(-x);
}
il void Add1(int x,int y){
while(x<=n){
c1[x]+=y;
x+=lowbit(x);
}
}
il int Ask1(int x){
int res=0;
while(x){
res+=c1[x];
x-=lowbit(x);
}
return res;
}
il void Add2(int x){
while(x<=n){
c2[x]++;
x+=lowbit(x);
}
}
il int Ask2(int x){
int res=0;
while(x){
res+=c2[x];
x-=lowbit(x);
}
return res;
}
il void solve(){
n=read(),m=read();
for(re int i=1;i<=n;i++)
a[i]=read(),b[i]=a[i];
memset(c1,0,sizeof c1);
memset(c2,0,sizeof c2);
vis.clear();
sort(b+1,b+1+n);
for(re int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+n,a[i])-b+(vis[a[i]]++);
for(re int i=1;i<=n;i++){
int l=0,r=n,mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(Ask1(mid)<=m-b[a[i]])ans=mid,l=mid+1;
else r=mid-1;
}
cout<<i-1-Ask2(ans)<<' ';
Add1(a[i],b[a[i]]);
Add2(a[i]);
}
putchar('\n');
}
signed main(){
freopen("gohome.in","r",stdin);
freopen("gohome.out","w",stdout);
t=read();
while(t--)solve();
return 0;
}