[Apio2012]dispatching（派遣）——线段树合并

桃扇骨 2021-11-22 05:16 305阅读 0赞

题面

[Bzoj2809][]

解析

按照贪心策略我们想选尽量多的人，所以就会选费用少的人，那么对于每个节点可以建一棵值域线段树，父亲的线段树由他的所有儿子的线段树合并再单点修改而来，这样就可以快速查询有多少个数满足要求， 线段树上维护人数以及费用和， 考虑到值域有1e9， 而人数只有1e5，我们考虑离散化，因为每个节点都有一棵对应的线段树，所以我们动态开点，以压缩空间。那么接下来的问题就在于如何合并线段树了，我们设要把y号节点合并到x号节点内，分别考虑左右儿子，如果x有左儿子，则向下递归， 如果y号节点没有左儿子就返回， 或者如果达到L == R， 就合并信息； 如果y有左儿子而x没有，那就直接把y号节点的左儿子赋给x的左儿子，返回。右儿子的操作是一样的。

还有一个在合并线段树时的小优化，如果左儿子的sum已经大于m了， 就更新父亲节点的信息，不合并右儿子，直接返回，好像的确快些。

其余细节详见代码。

代码：

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

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 100005;
    
    template<class T> void read(T &re)
    {
        re=0;
        T sign=1;
        char tmp;
        while((tmp=getchar())&&(tmp<'0'||tmp>'9')) if(tmp=='-') sign=-1;
        re=tmp-'0';
        while((tmp=getchar())&&(tmp>='0'&&tmp<='9')) re=(re<<3)+(re<<1)+(tmp-'0');
        re*=sign;
    }
    
    int tot, root[maxn], n, m, w[maxn], v[maxn], mas, aw[maxn], cnt, f[maxn];
    ll ans;
    
    struct seg_tree{
        int ls, rs, num;
        ll sum;
    }tr[maxn * 20];
    
    void update(int x)
    {
        tr[x].num = tr[tr[x].ls].num + tr[tr[x].rs].num ;
        tr[x].sum = tr[tr[x].ls].sum + tr[tr[x].rs].sum ;
    }
    
    void Merge(int x, int y, int L, int R)
    {
        if(!y)    return ;
        if(L == R)
        {
            tr[x].num += tr[y].num;
            tr[x].sum += tr[y].sum;
            return ;
        }
        int mid = (L + R)>>1;
        if(tr[x].ls)
            Merge(tr[x].ls, tr[y].ls, L, mid);
        else
            tr[x].ls = tr[y].ls;
        if(tr[tr[x].ls].sum > m)
        {
            update(x);
            return ;
        }    
        if(tr[x].rs)
            Merge(tr[x].rs, tr[y].rs, mid + 1, R);
        else
            tr[x].rs = tr[y].rs;
        update(x);
    }
    
    void Modify(int x, int val, int L, int R)
    {
        if(L == R)
        {
            tr[x].num ++;
            tr[x].sum += aw[val];
            return ;
        }
        int mid = (L + R)>>1;
        if(val <= mid)
        {
            if(!tr[x].ls)
                tr[x].ls = ++tot;
            Modify(tr[x].ls, val, L, mid);
        }
        else
        {
            if(!tr[x].rs)
                tr[x].rs = ++tot;
            Modify(tr[x].rs, val, mid + 1, R);
        }
        update(x);
    }
    
    int Query(int x, int L, int R, ll rest)
    {
        if(rest >= tr[x].sum)
            return tr[x].num;
        if(L == R)
            return rest / aw[L];
        int mid = (L + R)>>1, ret = 0;
        if(tr[x].ls && rest <= tr[tr[x].ls].sum)
            ret += Query(tr[x].ls, L, mid, rest);
        else if(tr[x].rs)
        {
            ret += tr[tr[x].ls].num ;
            ret += Query(tr[x].rs, mid + 1, R, rest - tr[tr[x].ls].sum);
        }    
        return ret;
    }
    
    int main()
    {
        read(n);read(m);
        for(int i = 1; i <= n; ++i)
        {
            root[i] = ++tot;
            int x, y, z;
            read(x);read(y);read(z);
            f[i] = x;
            aw[i] = w[i] = y;
            v[i] = z;
        }
        sort(aw + 1, aw + n + 1);
        cnt = unique(aw + 1, aw + n + 1) - aw - 1;
        for(int i = n; i; --i)
        {
            Modify(root[i], lower_bound(aw + 1, aw + cnt + 1, w[i]) - aw, 1, cnt);
            ans = max(ans, 1LL * v[i] * Query(root[i], 1, cnt, (ll)m));
            if(f[i])
                Merge(root[f[i]], root[i], 1, cnt);
        }
        printf("%lld", ans);
        return 0;
    }

转载于:https://www.cnblogs.com/Joker-Yza/p/11235656.html

[Bzoj2809]: https://www.lydsy.com/JudgeOnline/problem.php?id=2809
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/fca2911b2bb5460284dcb7dd9ee860a1.png