【BZOJ5469】[FJOI2018]领导集团问题（动态规划，线段树合并）

题面

BZOJ

洛谷

题解

题目就是让你在树上找一个最大的点集，使得两个点如果存在祖先关系，那么就要满足祖先的权值要小于等于儿子的权值。

首先离散权值。

考虑一个暴力\(dp\)，设\(f[i][j]\)表示以\(i\)为根，子树中被选择的最小值为\(j\)时能够被选出的最大点树。然后xjb转移一下就写出了一个\(O(n^3)\)的优秀做法。

然后把状态从恰好变成至少，然后就得到了一个\(O(n^2)\)的做法。

考虑\(O(n^2)\)的\(dp\)，本质上就是在维护一个后缀的最大值。

不难发现后缀最大值一定是不降的。

考虑对于后缀进行差分，每次相当于现在\(w[i]\)位置加一，然后往前更新一段，直到下一个差分数组上有\(1\)的位置。

那么用线段树合并就可以解决这个问题，给\(w[i]\)位置加一，然后线段树上二分找到上一个为\(1\)的位置然后把它减一就好了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAX 200200

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX<<1];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

int n,ans,w[MAX],S[MAX],tot,rt[MAX];

int ls[MAX*18],rs[MAX*18],t[MAX*18],node;

void Modify(int &x,int l,int r,int p)

{

	if(!x)x=++node;t[x]+=1;if(l==r)return;

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

	if(p<=mid)Modify(ls[x],l,mid,p);

	else Modify(rs[x],mid+1,r,p);

}

bool Flag;

void Calc(int x)

{

	if(!x)return;t[x]-=1;

	if(t[rs[x]])Calc(rs[x]);

	else Calc(ls[x]);

}

void Minus(int x,int l,int r,int p)

{

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

	if(p<=mid)Minus(ls[x],l,mid,p);

	else

	{

		Minus(rs[x],mid+1,r,p);

		if(!Flag&&t[ls[x]])Flag=true,Calc(ls[x]);

	}

	if(Flag)t[x]-=1;

}

void Merge(int &x,int &y)

{

	if(!x||!y){x|=y;return;}t[x]+=t[y];

	Merge(ls[x],ls[y]);Merge(rs[x],rs[y]);

}

void dfs(int u)

{

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

		dfs(e[i].v),Merge(rt[u],rt[e[i].v]);

	Modify(rt[u],1,tot,w[u]);

	Flag=false;Minus(rt[u],1,tot,w[u]);

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)S[++tot]=w[i]=read();

	for(int i=2;i<=n;++i)Add(read(),i);

	S[++tot]=1e9+1;sort(&S[1],&S[tot+1]);tot=unique(&S[1],&S[tot+1])-S-1;

	for(int i=1;i<=n;++i)w[i]=lower_bound(&S[1],&S[tot+1],w[i])-S;

	dfs(1);printf("%d\n",t[rt[1]]);

	return 0;

}