[Apio2012]dispatching 主席树做法

bzoj 2809: [Apio2012]dispatching

http://www.lydsy.com/JudgeOnline/problem.php?id=2809

Description

在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为 Master。除了 Master以外，每名忍者都有且仅有一个上级。为保密，同时增强忍者们的领导力，所有与他们工作相关的指令总是由上级发送给他的直接下属，而不允许通过其他的方式发送。现在你要招募一批忍者，并把它们派遣给顾客。你需要为每个被派遣的忍者支付一定的薪水，同时使得支付的薪水总额不超过你的预算。另外，为了发送指令，你需要选择一名忍者作为管理者，要求这个管理者可以向所有被派遣的忍者发送指令，在发送指令时，任何忍者（不管是否被派遣）都可以作为消息的传递人。管理者自己可以被派遣，也可以不被派遣。当然，如果管理者没有被排遣，就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平，其中每个忍者的领导力水平也是一定的。写一个程序，给定每一个忍者 i的上级 Bi，薪水Ci，领导力L i，以及支付给忍者们的薪水总预算 M，输出在预算内满足上述要求时顾客满意度的最大值。

1 ≤N ≤ 100,000 忍者的个数；

1 ≤M ≤ 1,000,000,000 薪水总预算；

0 ≤Bi < i 忍者的上级的编号；

1 ≤Ci ≤ M 忍者的薪水；

1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。

Input

从标准输入读入数据。

第一行包含两个整数 N和 M，其中 N表示忍者的个数，M表示薪水的总预算。

接下来 N行描述忍者们的上级、薪水以及领导力。其中的第 i 行包含三个整 Bi , C i , L i分别表示第i个忍者的上级，薪水以及领导力。Master满足B i = 0，并且每一个忍者的老板的编号一定小于自己的编号 Bi < i。

Output

输出一个数，表示在预算内顾客的满意度的最大值。

Sample Input

5 4
0 3 3
1 3 5
2 2 2
1 2 4
2 3 1

Sample Output

HINT

如果我们选择编号为 1的忍者作为管理者并且派遣第三个和第四个忍者，薪水总和为 4，没有超过总预算。

因为派遣了2 个忍者并且管理者的领导力为 3，用户的满意度为 6 ，是可以得到的用户满意度的最大值。

题目剖析：

ans=领导力*个数

领导力：枚举每个忍者

个数：当然是需要薪水少的先派遣啦

所以，节点的领导力为a，在以这个节点为根的子树中（包括这个节点），从小到大选尽可能多的节点s，满足节点的薪水和<=总预算，最大化a*s

这道题还可以用左偏树来做，但蒟蒻一枚只会主席树，所以这里只写主席树做法

推荐黄学长的博客，维护子树大根堆，用可并堆将时间复杂度降为nlongn http://hzwer.com/5682.html

数据结构：主席树

辅助：dfs序（开始没想到）

以忍者的dfs序为下标，薪水为区间建立主席树

首先说说dfs序

1、为什么需要dfs序？

因为派遣忍者的范围是以这个忍者为根的子树。

假设当前节点为i，遍历到时令 in[i]=a，表示i是第a个被遍历。以i为节点的子树遍历完后，令out[i]=b,b为当前所有已遍历节点总数

那么这个节点可以派遣的范围是dfs序[a,b]（包括a，b）之间的忍者

所dfs序的作用是锁定查找区间

2、如何构造dfs序？（自己也没想到）

令t表示当前已遍历节点总数，每遍历一个节点t++，设当前节点为i，遍历到i是in[i]=t，i退出时out[i]=t

在构造dfs序时，顺便记录下dfs序为i的忍者的薪水、领导力，然后按照dfs序在主席树中插入节点

最后是查找

枚举每个忍者，查找他的派遣范围最多能派遣多少个忍者

如果做过[CQOI2015]任务查询系统，会知道那道题在查询查到叶子节点时，对答案的贡献是sum[l]/count[l]*k

本题查询的是数量，到叶子节点时有没有坑呢？

有。叶子节点对答案有贡献的忍者数量应该是 min(薪水预算/派遣这个节点的忍者所需薪水，这个节点的忍者个数)

这里的节点是主席树中以薪水为区间建立的节点

还有就是要注意答案用long long

#include<cstdio>
#include<algorithm>
#define N 100001
using namespace std;
int n,m,money[N],lead[N],front[N],next[N];
int hash[N],cnt_money;
int in[N],out[N],t;
int root[N],tot,lc[N*20],rc[N*20],cnt[N*20];
long long sum[N*20],ans,dispatch;
struct node
{
    int mon,lea;
}e[N];
inline void add(int u,int v)
{
    next[v]=front[u];
    front[u]=v;
}
inline int dfs(int r)
{
    in[r]=++t;
    e[t].lea=lead[r];e[t].mon=hash[r];
    if(front[r])
        for(int i=front[r];i;i=next[i])
            dfs(i);
    out[r]=t;
}
void discrete()
{
    sort(money+1,money+n+1);    
    cnt_money=unique(money+1,money+n+1)-(money+1);
    for(int i=1;i<=n;i++) hash[i]=lower_bound(money+1,money+cnt_money+1,hash[i])-money;
}
inline void insert(int pre,int & now,int l,int r,int w)
{
    sum[now=++tot]=sum[pre]+money[w];
    cnt[now]=cnt[pre]+1;
    if(l==r) return;
    int mid=l+r>>1;
    if(w<=mid)
    {
        rc[now]=rc[pre];
        insert(lc[pre],lc[now],l,mid,w);
    }
    else
    {
        lc[now]=lc[pre];
        insert(rc[pre],rc[now],mid+1,r,w);
    }
}
inline int query(int x,int y,int l,int r,long long k)
{
    if(l==r) return min(k/(long long)money[l],(long long)(cnt[y]-cnt[x]));
    int mid=l+r>>1;
    long long tmp=sum[lc[y]]-sum[lc[x]];
    if(k<=tmp) return query(lc[x],lc[y],l,mid,k);
    else return cnt[lc[y]]-cnt[lc[x]]+query(rc[x],rc[y],mid+1,r,k-tmp);
}
int main()
{
    scanf("%d%lld",&n,&m);
    int b,c,l;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&b,&money[i],&lead[i]);
        hash[i]=money[i];
        add(b,i);
    }
    discrete();
    dfs(front[0]);
    for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,cnt_money,e[i].mon); 
    for(int i=1;i<=n;i++)
    {
        int l=in[i],r=out[i];//l：节点i的dfs序，r节点i可以派遣的最靠后的忍者的dfs序 
        dispatch=query(root[l-1],root[r],1,cnt_money,m);
        ans=max(ans,(long long)lead[i]*dispatch);
    }
    printf("%lld",ans);
}

这道题做的时候

1、没有想到用dfs序锁定查找区间

2、ans=max(忍者的领导力*派遣忍者个数)，没有想到可以枚举每个忍者，这样就解决了领导力的问题。对答案的分解能力欠缺

3、答案没用long long，开始做的时候还想着答案用long long，想先写出来过了样例后再改，结果忘了

4、查询时，如果当前区间为[x,y]，要到节点的右孩子去查询，返回的答案应是区间左右端点左孩子的cnt差，而不是y的cnt。这里与任务查询系统混了，因为任务查询系统查询的区间是[0,y]，0可以省略，所以可以直接用y的cnt、sum