HDU 6609 답 찾기 (가중치 선분 트 리)

#include
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int sum[maxn<<2],a[maxn],b[maxn],val[maxn<<2];
void Updte(int p,int l,int r,int k)
{
    if(l == r)
    {
        sum[p] += b[l];
        val[p]++;
        return;
    }
    int mid = l + (r - l) / 2;
    if(k <= mid)
        Updte(p * 2,l,mid,k);
    else
        Updte(p * 2 + 1,mid + 1,r,k);
    sum[p] = sum[p * 2] + sum[p * 2 + 1];
    val[p] = val[p * 2] + val[p * 2 + 1];
}
int Query(int p,int l,int r,int v)
{
    int mid = l + (r - l) / 2;
    if(l == r)
    {
        if(!v || !b[l])
            return 0;
        return (v + (b[l] - 1)) / b[l];
    }
    if(sum[p * 2 + 1] < v)
        return Query(p * 2,l,mid,v - sum[p * 2 + 1]) + val[p * 2 + 1];
    return Query(p * 2 + 1,mid + 1,r,v);
}
signed main()
{
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        int n,m;
        scanf("%lld%lld",&n,&m);
        for(int i = 1;i <= n; i++)
        {
            scanf("%lld",&a[i]);
            b[i] = a[i];
        }
        sort(b + 1,b + 1 + n);
        int vl = unique(b + 1,b + 1 + n) - b - 1;
        for(int i = 1;i <= vl * 4; i++)
            sum[i] = val[i] = 0;
        int res = 0;
        for(int i = 1;i <= n; i++)
        {
            res += a[i];
            int ans = 0;
            if(res > m)
                ans = Query(1,1,vl,res - m);
            int k = lower_bound(b + 1,b + 1 + vl,a[i]) - b;
            Updte(1,1,vl,k);
            printf("%lld ",ans);
        }
        puts("");
    }
    return 0;
}