2019hdu多校第二次1007 Find the answer 线段树板子。

客官°小女子只卖身不卖艺 2021-11-17 02:50 140阅读 0赞

Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m. So what's the minimum number of chosen elements to meet the requirements above?.

Input

The first line contains an integer Q --- the number of test cases.   
For each test case:   
The first line contains two integers n and m --- n represents the number of elemens in sequence W and m is as described above.   
The second line contains n integers, which means the sequence W.  
  
1 <= Q <= 15   
1 <= n <= 2\*105   
1 <= m <= 109   
For each i, 1 <= Wi <= m

Output

For each test case, you should output n integers in one line: i-th integer means the minimum number of chosen elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m.

大概就是线段树每次查询之前有多少个数+现在的数  小于等于m，一个线段树就行了，

自己没看清数据范围，进行了离散化，其实不用的。但是！ 比赛的时候紧张了  然后离散化出了bug，debug一小时，艾，还是心态不稳，看到板子题就激动，激动就出错。下次注意

#include<bits/stdc++.h>
    using namespace std;
    #define LL long long
    const int M=2e5+50;
    struct Node{
    	int l,r;
    	LL sum,num; 
    }t[M*4];
    int d[M],b[M],n,m;
    void build(int k,int l,int r){
    	t[k].l=l;t[k].r=r;
    	t[k].sum=t[k].num=0;
    	if(l==r)return ;
    	int mid=(l+r)>>1;
    	build(k*2,l,mid);
    	build(k*2+1,mid+1,r);
    }
    void update(int k,int in){
    	t[k].num++;
    	if(t[k].l==t[k].r&&t[k].l==in){
    		t[k].sum+=b[in];
    		return ;
    	}
    	int mid=(t[k].l+t[k].r)>>1;
    	if(in<=mid)update(k*2,in);
    	if(mid<in)update(k*2+1,in);
    	t[k].sum=t[k*2].sum+t[k*2+1].sum;
    } 
    int query(int k,int now){
    	if(t[k].sum<=now)return t[k].num;
    	if(t[k].l==t[k].r)	return now/b[t[k].l];
    	int mid=(t[k].l+t[k].r)>>1;
    	if(t[k*2].sum<=now)	return t[k*2].num+query(k*2+1,now-t[k*2].sum); 
    	else return query(k*2,now);
    }
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&n,&m);
    		for(int i=1;i<=n;i++)scanf("%d",&d[i]),b[i]=d[i];	
    		sort(b+1,b+n+1);
    		int qz=unique(b+1,b+n+1)-(b+1);
    		for(int i=1;i<=n;i++)d[i]=lower_bound(b+1,b+qz+1,d[i])-b;
    		build(1,1,qz);
    		update(1,d[1]);
    		printf("0 ");
    		for(int i=2;i<=n;i++){
    			printf("%d ",i-1-query(1,m-b[d[i]]));
    			update(1,d[i]);
    		}
    		printf("\n");
    	}
    	return 0;
    }