题意是说,有一个给定的序列\(W\)与整数\(m\),对于\(W\)的前\(k\)项,删掉\(d_k\)项就可以该子序列的前缀和不大于\(m\)。问对于\(W\)的所有前缀子序列,其最小的\(d\)分别是多少。
思路就是通过线段树维护区间和以及区间中数字个数,查询时二分找到符合要求的区间,查询其数字个数,此时的数字个数是需要保留下来的数字的个数,因此答案应该是\(i-1-tmp\)(\(tmp\)为查询结果)。另外,该题数据范围比较大,需要做离散化。
代码如下:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <utility>
#include <map>
#include <stack>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
#define INF 0x3f3f3f3f
#define int long long
#define IOS std::ios::sync_with_stdio(false)
const int maxn=200005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int sum[maxn<<2];
int cnt[maxn<<2];
ll arr[maxn],lisan[maxn];
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
cnt[rt]=cnt[rt<<1]+cnt[rt<<1|1];
}
void build(int lef,int rig,int rt)
{
if(lef==rig){
sum[rt]=cnt[rt]=0;
return ;
}
int mid=lef+(rig-lef)/2;
build(lson);
build(rson);
pushup(rt);
}
void update(int pos,int lef,int rig,int rt)
{
if(lef==rig){
sum[rt]+=lisan[pos];
cnt[rt]++;
return ;
}
int mid=lef+(rig-lef)/2;
if(pos<=mid)
update(pos,lson);
else
update(pos,rson);
pushup(rt);
}
int query(ll val,int lef,int rig,int rt)
{
if(sum[rt]<=val)
return cnt[rt];
if(lef==rig){
if(cnt[rt]==0)
return 0;
return val/(sum[rt]/cnt[rt]);
}
int mid=lef+(rig-lef)/2;
if(sum[rt<<1]>val)
return query(val,lson);
else
return cnt[rt<<1]+query(val-sum[rt<<1],rson);
}
int ans[maxn];
int32_t main()
{
IOS;
int t;cin>>t;
while(t--){
int n;cin>>n;
ll m;cin>>m;
for(int i=1;i<=n;i++){
cin>>arr[i];
lisan[i]=arr[i];
}
sort(lisan+1,lisan+1+n);
int len=unique(lisan+1,lisan+1+n)-lisan-1;
build(1,len,1);
for(int i=1;i<=n;i++){
int idx=lower_bound(lisan+1,lisan+1+n,arr[i])-lisan;
int tmp=query(m-arr[i],1,len,1);
update(idx,1,len,1);
ans[i]=i-tmp-1; //tmp是可以保留下来的数的个数
}
for(int i=1;i<=n;i++)//
cout<<ans[i]<<" ";
cout<<"\n";
}
return 0;
}