HDU 6609 权值线段树

发表于 | 分类于 | 阅读次数：

比赛开始直接优先队列乱搞，TLE。。

题目链接

题意

问你最小需要删多少个数字才能使得从第一个数到第i个数字的和<= m，第i个数字不能删。

思路

我们自然想到删除尽量大的数字，但是如果我们当前访问到第i个数字时，总是对前i - 1个数字进行排序肯定会超时。我们可以建立一棵从第一个数字到当前数字的权值线段树，每个节点记录当前区间内数字和以及个数。这样我们就可以根据权值线段树进行查找，利用权值线段树的原因是权值线段树本身也是一棵有序的树，查找是可以二分的。这样就达到了查询O(logn)复杂度。本身权值线段树我是一直用主席树写的，但是这个题目会MLE，再者，这个题目每次都是查询前i个数，因此建一颗线段树即可，查询完毕再更新下一个数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-10;
const int maxn = 200005;

struct node{
   ll num, sum;
}tr[maxn << 2];
int a[maxn],b[maxn];
void build(int node, int l, int r)
{
    tr[node].num = 0, tr[node].sum = 0;
    if(l == r){
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1|1, mid + 1, r);
}

void update(int node, int l, int r, int pos)
{
    if(l == r && l == pos)
    {
        tr[node].num++;
        tr[node].sum += b[pos];
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(node << 1, l, mid, pos);
    else update(node << 1|1, mid + 1, r, pos);
    tr[node].sum = tr[node << 1].sum + tr[node << 1|1].sum;
    tr[node].num = tr[node << 1].num + tr[node << 1|1].num;
}

int query(int node, int l, int r, int value)
{
    if(l == r)
    {
        if(tr[node].sum > value) return value / b[l];
        return tr[node].num;
    }
    int mid = (l + r ) >> 1;
    if(tr[node << 1].sum <= value){
        return tr[node << 1].num + query(node <<1|1, mid + 1, r, value - tr[node << 1].sum);
    }
    else{
        return query(node << 1, l, mid, value);
    }
}
int tot;
int getid(int x)
{
    int id = lower_bound(b + 1,b + tot + 1, x) - b;
    return id;
}
int main()
{
    int T,n,m;
    cin >> T;
    while(T--)
    {
        scanf("%d %d",&n,&m);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
            b[i] = a[i];
        }
        sort(b + 1, b + n + 1);
        tot = unique(b + 1, b + n + 1) - b - 1;
        build(1,1,tot);
        update(1,1,tot,getid(a[1]));
        cout << 0 << ' ';
        for(int i = 2; i <= n; ++i)
        {
            int Num = query(1,1,tot,m - a[i]);
            cout <<  i - 1 - Num << ' ';
            update(1,1,tot,getid(a[i]));
        }
        cout << '\n';
    }
}