Find the answer

题意是说,有一个给定的序列\(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;
}