[权值线段树]

Find the answer

Description

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.

Examples

Input

7 15

1 2 3 4 5 6 7

5 100

80 40 40 40 60

Output

0 0 0 0 0 2 3

0 1 1 2 3

正确解法：

对于每一个i来说，使前面尽可能多的a[j]+a[i] <=m （j<i）

也就是说对前面 i-1 个数排序，找最多的个数。使他们加起来 <= m-a[i]

我们用权值线段树来搞。

权值线段树什么意思呢？就是类似一个桶排序的东西，树的节点统计个数。

当 l==r==a[l]　　tree[rt]++;

树的范围就是a[i]，可题目中a[i]<=1e9，所以我们要离散化。

对于每个i来说，我们找最多的小数个数　　res=m-a[i];

我们查询 1-cnt 中 1-mid 数的总和，若左儿子的总和小于res 的话，那就左儿子的个数+查询右儿子。

else 查询左儿子。

查询过a[i]后，我们把a[i]放进树中。

1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 #include<string>
 6 #include<map>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<cmath>
11 #include<cstdlib>
12 #include<stack>
13 #define de printf("\ndebug:\n")
14 #define End printf("\nend\n\n")
15 #define fi first
16 #define se second
17 #define P pair< int, int >
18 #define PII pair< pair<int, int> ,int>
19 #define INF 0x3f3f3f3f
20 using namespace std;
21 typedef long long ll;
22 const int mod1=1e5+7;
23 const int N=2e5+100;
24 const int mod2=1e9+7;
25 const ll mod3=1e12+7;
26 int T,n,m;
27 int a[N],b[N],cnt=0,c[N];
28 ll tree[N*4],totsum[N*4];
29 void push_up(int rt)
30 {
31     tree[rt]=tree[rt<<1]+tree[rt<<1|1];
32     totsum[rt]=totsum[rt<<1]+totsum[rt<<1|1];
33 }
34 void update(int x,int l,int r,int rt)
35 {
36     if(l==r)
37     {
38         tree[rt]++;
39         totsum[rt]+=b[x];
40         return ;
41     }
42     int mid=l+r>>1;
43     if(x<=mid)  update(x,l,mid,rt<<1);
44     else    update(x,mid+1,r,rt<<1|1);
45     push_up(rt);
46 }
47 int query(int l,int r,int rt,int res)
48 {
49     if(l==r)
50     {
51         return res/b[l];
52     }
53     ll sum=totsum[rt<<1];
54     int mid=l+r>>1;
55     if(sum>=res)
56         return query(l,mid,rt<<1,res);
57     else
58         return tree[rt<<1]+query(mid+1,r,rt<<1|1,res-sum);
59 }
60 int main()
61 {
62     scanf("%d",&T);
63     while(T--)
64     {
65         scanf("%d%d",&n,&m);
66         memset(tree,0,sizeof(tree));
67         memset(totsum,0,sizeof(totsum));
68         for(int i=1;i<=n;i++)
69         {
70             scanf("%d",&a[i]);
71             b[i]=a[i];
72         }
73         sort(b+1,b+n+1);
74         cnt=unique(b+1,b+n+1)-b-1;
75         for(int i=1;i<=n;i++)
76             c[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
77         ll tot=0;
78         for(int i=1;i<=n;i++)
79         {
80             tot+=a[i];
81             if(tot<=m)
82                 printf("0 ");
83             else
84             {
85                 int ans=query(1,cnt,1,m-a[i]);
86                 printf("%d ",i-ans-1);
87             }
88             update(c[i],1,cnt,1);
89         }
90         printf("\n");
91     }
92 
93 
94     return 0;
95 }