P1552 [APIO2012]派遣

标签：root   oid   har   show   fine   lld   names   efi   back   

链接

https://www.luogu.org/problemnew/show/P1552

思路

忍者数量肯定越多越好
那就从下到上的合并它的孩子
左偏树的话
顺便维护一个tot，大头堆，如果tot大于了m，把大的删掉
如果左偏树忘干净了或者没学的话
线段树合并也是个不错的选择
直接权值线段树合并就好，内存30倍会炸，也许是我没离散化的缘故吧
查询在上面二分

左偏树代码

#include 
#define FOR(i,a,b) for(int i=a;i'9'||s='0'&&smone) rt=delet(rt);
    ans=max(ans,xs[u]*(ll)size[rt]);
    return rt;
}
int main() {
    n=read(),mone=read();
    int root;
    FOR(i,1,n) {
        int x=read();
        val[i]=read();xs[i]=read();
        sum[i]=val[i];size[i]=1;
        if(x) add_edge(x,i);
        else root=i;
    }
    int wuyong=dfs(root);
    cout

线段树合并代码

#include 
#include 
#include 
#include 
#include 
#define ll long long
using namespace std;
const int N=1e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s='0'&&s G[N];
struct node {
    int l,r,siz;
    ll tot;
}e[N*30];
void pushup(int rt) {
    e[rt].siz=e[e[rt].l].siz+e[e[rt].r].siz;
    e[rt].tot=e[e[rt].l].tot+e[e[rt].r].tot;
}
int cnt;
void insert(int l,int r,int L,int &rt) {
    rt=++cnt;
    if(l==r) {
        e[rt].siz++;
        e[rt].tot+=l;
        return;
    }
    int mid=(l+r)>>1;
    if(L>1;
    e[x].l=merge(l,mid,e[x].l,e[y].l);
    e[x].r=merge(mid+1,r,e[x].r,e[y].r);
    pushup(x);
    return x;
}
int query(int l,int r,int k,int rt) {
    if(l==r) return k>=e[rt].tot ? e[rt].siz : 0;
    int mid=(l+r)>>1;
    if(e[e[rt].l].tot>=k) return query(l,mid,k,e[rt].l);
    else return e[e[rt].l].siz+query(mid+1,r,k-e[e[rt].l].tot,e[rt].r);
}
ll ans;
void dfs(int u) {
    insert(1,1000000000,money[u],rt[u]);
    for(vector::iterator it=G[u].begin();it!=G[u].end();++it) {
        dfs(*it);
        rt[u]=merge(1,1000000000,rt[u],rt[*it]);
    }
    ans=max(ans,(ll)leader[u]*query(1,1000000000,m,rt[u]));
}
int main() {
    n=read(),m=read();
    for(int i=1;i

P1552 [APIO2012]派遣

标签：root   oid   har   show   fine   lld   names   efi   back   

原文地址：https://www.cnblogs.com/dsrdsr/p/10359546.html