BZOJ2809&&LG1552 APIO2012派遣(线段树合并)

题面

自己找去

HINT

简化一题面就是让你从每个点的子树中以\(<=m\)的代价选取尽可能多的点，然后乘上子树根的一个属性值，每个点做一遍取个\(max\)。看大家都是什么可并堆、dfs序+主席树，我的做法是对于每个节点开一颗权值线段树，每个节点维护\(size\)和\(tot\)，然后修改和线段树合并都是常规写法。

着重讲一下查询

这样的写法之后就是要实现查询用m的代价可以最多选择多少个点

inline int query(int p,long long rk,int l,int r){

        if(!p) return 0;//如果进入了空节点，就肯定没有可选的，返回0

        if(l==r){

            int x=st[p].tot/st[p].size;return min((long long)rk/x,(long long)st[p].size);

//这里是重点，查询到该点的时候我还有rk的剩余，已经到叶子节点了，这个时候我们就要计算一下自己最多可以选多少个，如果能都选就都选，如果不能多选就尽量选满

        }

        long long now=st[ls(p)].tot;int mid=(l+r)>>1;

        if(rk<=now) return query(ls(p),rk,l,mid);

        else return st[ls(p)].size+query(rs(p),rk-now,mid+1,r);

    }

其他的看代码吧

#include<bits/stdc++.h>

#define INF 0x3f3f3f3f

#define ls(x) st[x].ch[0]

#define rs(x) st[x].ch[1]

using namespace std;

inline int read(){

    int w=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9'){

        w=(w<<3)+(w<<1)+ch-48;

        ch=getchar();

    }

    return w*f;

}

int n,m,cur,root[100010],a[100010],b[100010],val[100010],now[100010];

long long l[100010],ans[100010];

bool debug;

struct CHAIRMANTREE{

    struct Node{

        int size,ch[2];long long tot;

    }st[6000010];

    int tot;

    inline void pushup(int x){

        st[x].size=st[ls(x)].size+st[rs(x)].size;

        st[x].tot=st[ls(x)].tot+st[rs(x)].tot;return;

    }

    inline int change(int p,int l,int r,int pos,int val){

        if(!p)p=++tot;

        if(l==r){

            st[p].size+=1;st[p].tot+=val;return p;

        }

        int mid=(l+r)>>1;

        if(pos<=mid) ls(p)=change(ls(p),l,mid,pos,val);

        else rs(p)=change(rs(p),mid+1,r,pos,val);

        pushup(p);return p;

    }

    inline int merge(int x,int y,int l,int r){

        if(!x||!y) return x|y;

        int p=++tot;

        if(l==r){

            st[p].size=st[x].size+st[y].size;

            st[p].tot=st[x].tot+st[y].tot;return p;

        }

        int mid=(l+r)>>1;

        ls(p)=merge(ls(x),ls(y),l,mid);

        rs(p)=merge(rs(x),rs(y),mid+1,r);

        pushup(p);return p;

    }

    inline int query(int p,long long rk,int l,int r){

        if(!p) return 0;

        if(l==r){

            int x=st[p].tot/st[p].size;return min((long long)rk/x,(long long)st[p].size);

        }

        long long now=st[ls(p)].tot;int mid=(l+r)>>1;

        if(rk<=now) return query(ls(p),rk,l,mid);

        else return st[ls(p)].size+query(rs(p),rk-now,mid+1,r);

    }

}TREE;

int cnt,head[100010];

struct Edge{

    int from,to,next;

}edge[200010];

inline void addedge(int u,int v){

    cnt++;

    edge[cnt].from=u;

    edge[cnt].to=v;

    edge[cnt].next=head[u];

    head[u]=cnt;

}

map<int,int> mapp;

inline void prework(){

    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++){

        if(!mapp[a[i]]){

            cur++;mapp[a[i]]=cur;b[cur]=a[i];

        }

    }

    for(int i=1;i<=n;i++){

        val[i]=mapp[val[i]];

    }

}

inline void dfs(int u){

    root[u]=TREE.change(root[u],1,cur,val[u],now[u]);

    for(int i=head[u];i;i=edge[i].next){

        int v=edge[i].to;dfs(v);

        root[u]=TREE.merge(root[u],root[v],1,cur);

    }

    if(debug)cout<<"test"<<u<<endl;

    ans[u]=(long long)TREE.query(root[u],m,1,cur);

    if(debug){

        cout<<u<<" "<<ans[u]<<endl;

    }

}

signed main(){

    n=read();m=read();

    for(int i=1;i<=n;i++){

        int x=read();addedge(x,i);

        now[i]=a[i]=val[i]=read();l[i]=read();

    }

    prework();

    //debug=true;

    dfs(1);

    long long Ans=-1;

    for(int i=1;i<=n;i++){

        //cout<<l[i]<<" "<<ans[i]<<endl;

        Ans=max(Ans,l[i]*ans[i]);

    }

    cout<<Ans<<endl;

    return 0;

}

巴特西

BZOJ2809&&LG1552 APIO2012派遣(线段树合并)

BZOJ2809&&LG1552 APIO2012派遣(线段树合并)

题面

HINT

着重讲一下查询

其他的看代码吧

最新文章

热门文章