BZOJ 4919 [Lydsy1706月赛]大根堆 (SRM08 T3)

【题解】

　　求一个序列的LIS有一个二分做法是这样的：f[i]表示长度为i的上升序列中最后一个数最小可以是多少，每次二分大于等于当前数字x的f[j]，把f[j]修改为x；如果找不到这样的f[j]，那就把长度加一并记录新的f（即f[++len]=x)

　　现在我们把这个做法放到树上，同样是可以做的。我们用set维护子树内的f数组，父节点在其孩子合并得到的set中二分第一个大于等于它的数字，换成父节点自己的值。合并子树的set直接启发式合并即可。两个log的复杂度。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<set>

 #define N 200010

 #define rg register

 #define LL long long

 using namespace std;

 int n,tot,last[N],val[N];

 multiset<int>f[N];

 struct edge{

     int to,pre;

 }e[N];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=='-'&&(f=-),c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 void dfs(int x,int fa){

     for(rg int i=last[x],to;i;i=e[i].pre){

         dfs(to=e[i].to,x);

         if(f[to].size()>f[x].size()) swap(f[x],f[to]);

         for(set<int>::iterator j=f[to].begin();j!=f[to].end();j++) f[x].insert(*j);

         f[to].clear();

     }

     if(f[x].size()>&&f[x].lower_bound(val[x])!=f[x].end()) f[x].erase(f[x].lower_bound(val[x]));

     f[x].insert(val[x]);

 }

 int main(){

     n=read();

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

         val[i]=read(); int fa=read();

         e[++tot]=(edge){i,last[fa]}; last[fa]=tot;

     }

     dfs(,);

     printf("%d\n",f[].size());

     return ;

 }

巴特西

BZOJ 4919 [Lydsy1706月赛]大根堆 (SRM08 T3)

最新文章

热门文章