大致题意
给定一个长度为 n 的序列 ai，给定一个前缀和上限 k。现要求对于每个 i ，要使前缀和 sum[i] 小于等于 k ，要至少删除前 1- (i-1) 的多少个数字。 （ 1< = n < = 2e5)
思路
(我那个沙雕对于一开始给我贪心然后递推，我diu，这tm 没有后效性的吗…) 这不就是插进来一个数，要求当前前缀和情况下挑最大的删，直到满足要求吗。 显然应该离散化，然后建一个权值线段树，线段树维护两个量，当前区间数的个数，还有当前区间权值和，设当前要删掉的值为s ,优先向右边寻找，如果右边的权值和不够，再向左边寻找。边界细节还是要注意一下。
代码
#include<bits/stdc++.h>
using namespace std
;
#define maxn 200005
#define maxm 1006
#define ll long long int
#define INF 0x3f3f3f3f
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
#define mem(a) memset(a,0,sizeof(a))
#define sqr(x) (x*x)
#define inf (ll)2e18+1
#define PI acos(-1)
#define mod 10007
#define auto(i,x) for(int i=head[x];i;i=ed[i].nxt)
#define ls x<<1
#define rs x<<1|1
ll
read(){
ll x
=0,f
=1ll;char ch
=getchar();
while(!isdigit(ch
)){if(ch
=='-')f
=-1;ch
=getchar();}
while(isdigit(ch
))x
=x
*10+ch
-'0',ch
=getchar();
return f
*x
;
}
int T
,n
,m
;
ll t
[maxn
<<2];
int siz
[maxn
<<2],a
[maxn
];
vector
<int>v
;
void pushup(int x
){
t
[x
]=t
[ls
]+t
[rs
];
siz
[x
]=siz
[ls
]+siz
[rs
];
}
void update(int x
,int l
,int r
,int pos
){
if(l
==r
){
t
[x
]+=1ll*v
[pos
];
siz
[x
]++;
return ;
}
int mid
=(l
+r
)>>1;
if(pos
<=mid
)update(ls
,l
,mid
,pos
);
else update(rs
,mid
+1,r
,pos
);
pushup(x
);
return ;
}
int query(int x
,int l
,int r
,ll sum
){
if(l
==r
){
return min(((sum
-1)/v
[l
])+1,1ll*siz
[x
]);
}
int mid
=(l
+r
)>>1;
if(t
[rs
]>=sum
)return query(rs
,mid
+1,r
,sum
);
else return siz
[rs
]+query(ls
,l
,mid
,sum
-t
[rs
]);
}
int main()
{
T
=read();
while(T
--){
n
=read();m
=read();
v
.clear();v
.push_back(-INF
);
mem(t
);mem(siz
);
inc(i
,1,n
)a
[i
]=read(),v
.push_back(a
[i
]);
sort(v
.begin(),v
.end());
int len
=unique(v
.begin(),v
.end())-v
.begin();
ll sum
=0;
inc(i
,1,n
){
sum
+=a
[i
];
if(sum
>m
)printf("%d ",query(1,1,n
,sum
-m
));
else printf("0 ");
int x
=lower_bound(v
.begin(),v
.begin()+len
,a
[i
])-v
.begin();
update(1,1,n
,x
);
}
printf("\n");
}
return 0;
}
