[权值线段树]

Love The Way You Lie 2021-11-01 04:38 358阅读 0赞

# 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\]放进树中。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

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 }

PS: CF中有一道很像的题目，就是数据范围小了一点，我们就可以真的用桶排序来写了。

[C2. Exam in BerSU (hard version)][C2. Exam in BerSU _hard version]

转载于:https://www.cnblogs.com/Kaike/p/11307427.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/c226076fcdb943c1b06ad14d7b275c49.png
[C2. Exam in BerSU _hard version]: http://codeforces.com/contest/1185/problem/C2