[权值线段树][比赛失误][x] HDU 6609 Find the answer

题目链接

题意：

给了 $N$ 个数 $W_k$ , 对于每个 $1 \le i \le n$, 在 $i$ 以前不包括 $i$ 的所有 $W$ 里选取最少的一些 $W$ 将其变为 $0$ ， 使得 从 $1$ 到 $i$ 的和不大于 $m$ 。要求对于每个 $i$ 输出最小的数目。

题解：

做的时候傻了，一直用set乱搞，搞来搞去总是tle，主要是用set维护真的会被卡。。用平衡树板子又有点大材小用，于是就米勒很久。

所以说遇到一个简单题很久没出的话，可能就得考虑全盘否定直接从来了。。。

如果一开始就没有被赵老师带着想set，而是直奔线段树去的话，就很好搞了，直接把问题转化为在前 i-1 个数里找出最少的数字使得之和大于 $pre[i]-m$ ，其中 $pre[i]$ 是前缀和。这样的话直接用权值线段树来做，每个节点存两个域，一个是数字的个数，一个是数字的和。。然后query的时候利用线段树天然的二分性质来搞就行了。。。

这题其实动机真的不难，就是因为不用数据结构的话每次要排序，然后权值线段树天生有排序的特性在里面。。。所以遇事不决还是先考虑线段树。。。不能一开始就想骚操作emmmmm

#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;

typedef long long ll;

const int maxn = 2e5;

ll a[maxn],has[maxn],cnt,n,m;

int Hash(ll x){
    return lower_bound(has+1,has+1+cnt,x)-has;
}

ll Ceil(ll a,ll b){
    return (a+b-1)/b;
}

ll sum[maxn<<2],num[maxn<<2];

void build(int o,int l,int r){
    if(l==r){
        sum[o]=num[o]=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    sum[o]=num[o]=0;
}

int p;ll v;
void update(int o,int l,int r){
    if(l==r){
        sum[o]+=has[p];
        num[o]++;
        return ;
    }
    int mid=(l+r)>>1;
    if(p<=mid) update(o<<1,l,mid);
    else update(o<<1|1,mid+1,r);
    sum[o]=sum[o<<1]+sum[o<<1|1];
    num[o]=num[o<<1]+num[o<<1|1];
}

ll an,cp,unit;

void query(int o,int l,int r){
    if(l==r){
        if(num[o]==0) return ;
        unit=sum[o]/num[o];
        an+=Ceil(cp,unit);
        return ;
    }
    int mid=(l+r)>>1;
    if(sum[o<<1|1]>=cp) 
        query(o<<1|1,mid+1,r);
    else {
        cp-=sum[o<<1|1];
        an+=num[o<<1|1];
        query(o<<1,l,mid);
    }
}

ll pre;
void init(){
    build(1,1,cnt);
    pre=0;
}

int main() {
	int T;
    
    scanf("%d",&T);
	while (T--){
        scanf("%lld%lld",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            has[i]=a[i];
        }
        sort(has+1,has+1+n);
        cnt=1;
        for(int i=2;i<=n;i++)
            if(has[cnt]!=has[i]) has[++cnt]=has[i];
        init();
        for(int i=1;i<=n;i++){
            pre+=a[i];
            cp=pre-m;
            an=0;
            query(1,1,cnt);
            printf("%d ",an);
            p=Hash(a[i]);
            update(1,1,cnt);
        }
        puts("");
	}
	return 0;
}