bzoj 2809: [Apio2012]dispatching【dfs序+主席树】

可并堆就可以，但是想复健一下主席树。

考虑枚举管理者，然后选忍者的时候在子树中贪心的从小到大选。做成dfs序就是选区间内和小于等于k的最多点。可以用主席树，查询的时候在主席树上二分即可

这里注意，为了方便起见，离散化的时候即使值相同也离散成不同值，这样可以保证主席树叶子结点的size最大为1，方便二分

#include<iostream>

#include<cstdio>

#include<map>

#include<algorithm>

using namespace std;

const int N=200005;

int n,m,h[N],cnt,a[N],dfn,rt[N],tot,g[N],l[N],r[N],ss,sk,mp[N];

long long c[N],d[N],ans;

struct qwe

{

	int ne,to;

}e[N];

struct zxs

{

	int l,r,ls,rs,s;

	long long sum;

}t[3000005];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

inline bool cmp(const int &a,const int &b)

{

	return c[a]<c[b];

}

inline void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	h[u]=cnt;

}

inline void dfs(int u)

{

	a[++dfn]=u;

	l[u]=dfn;

	for(int i=h[u];i;i=e[i].ne)

		dfs(e[i].to);

	r[u]=dfn;

}

void build(int &ro,int l,int r)

{

	ro=++tot;

	t[ro].l=l,t[ro].r=r;

	if(l==r)

		return;

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

	build(t[ro].ls,l,mid);

	build(t[ro].rs,mid+1,r);

}

void ins(int &ro,int pr,int v,int w)

{

	ro=++tot;

	t[ro]=t[pr];

	t[ro].s++;

	t[ro].sum+=w;

	if(t[ro].l==t[ro].r)

		return;

	int mid=(t[ro].l+t[ro].r)>>1;

	if(v<=mid)

		ins(t[ro].ls,t[pr].ls,v,w);

	else

		ins(t[ro].rs,t[pr].rs,v,w);

}

int ques(int l,int r,long long k)

{

	if(t[l].l==t[l].r)

	{

		if(t[r].sum-t[l].sum!=0&&sk+t[r].sum-t[l].sum<=m)

			return ss+1;

		else

			return ss;

	}

	long long now=t[t[r].ls].sum-t[t[l].ls].sum;

	if(now>=k)

		return ques(t[l].ls,t[r].ls,k);

	else

	{

		ss+=t[t[r].ls].s-t[t[l].ls].s;

		sk+=now;

		return ques(t[l].rs,t[r].rs,k-now);

	}

}

int main()

{

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

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

	{

		int b=read();g[i]=i,c[i]=read(),d[i]=read();

		add(b,i);

	}

	sort(g+1,g+1+n,cmp);

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

		mp[g[i]]=i;

	dfs(1);

	build(rt[0],1,n);

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

		ins(rt[i],rt[i-1],mp[a[i]],c[a[i]]);

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

	{

		ss=0,sk=0;

		ans=max(ans,d[i]*ques(rt[l[i]-1],rt[r[i]],m));

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

bzoj 2809: [Apio2012]dispatching【dfs序+主席树】

最新文章

热门文章