Tag:Line tree merge
Article From:https://www.cnblogs.com/yinwuxiao/p/9060320.html

The answer:

I think data structure is still necessary.

Because there are two identical data structures in one question, because the names are very easy to make mistakes.

 In addition, segmenttree () {} is used for initialization

The first naked DP is very nice

f[i][j]The maximum value of the point at the I point, the maximum value of < the point number of the =j

After reading other people’s questions, we know that we can use line segment tree merging to optimize this thing.

We consider each point, first we need to merge its subtree.

In fact, it is the addition of points in the same position.

Then, considering the current node, we apply f[v[x]-1]+1 to update the value between v[x]-n (that is to take Max operation).

Otherwise, it’s not down.

1.When x, y has a left second

You need to add a sum tag to it

The reason is, because he has no left son, it shows that the lazy value of the corresponding left second son is this.

So we need to become sum tags and add this to every child node.

2.downWhen you use lazy[fa] to update lazy[x], the reason is that there is sum[x].

#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
const int INF=1e9;
#define IL inline
#define rint register int
int n,m,fa[N],vv[N],head[N],l;
struct re{
  int a,b;
}a[N],v[N];
IL int max(int x,int y)
{
  int z;
  x>y?z=x:z=y;
  return(z);
}
IL int min(int x,int y)
{
  int z;
  x<y?z=x:z=y;
  return(z);
}
void arr(int x,int y)
{
  a[++l].a=head[x];
  a[l].b=y;
  head[x]=l;
}
struct segmenttree
{
  int cnt,rt[N],sum[N*20],ls[N*20],rs[N*20],lz[N*20];
  #define mid ((h+t)>>1)
  segmenttree(){cnt=0;}
  IL void down(int x)
  {
    if (ls[x]) lz[ls[x]]=max(sum[x]+lz[ls[x]],lz[x]),sum[ls[x]]+=sum[x];
    if (rs[x]) lz[rs[x]]=max(sum[x]+lz[rs[x]],lz[x]),sum[rs[x]]+=sum[x];
    sum[x]=0;
  }
  int merge(int x,int y)
  {
    if (!x||!y) return x^y;
    down(x); down(y);
    if (!ls[x])
      ls[x]=ls[y],lz[ls[x]]+=lz[x],sum[ls[x]]+=lz[x];
    else if (!ls[y])
      lz[ls[x]]+=lz[y],sum[ls[x]]+=lz[y];
    else ls[x]=merge(ls[x],ls[y]);
    if (!rs[x])
      rs[x]=rs[y],lz[rs[x]]+=lz[x],sum[rs[x]]+=lz[x];
    else if (!rs[y])
      lz[rs[x]]+=lz[y],sum[rs[x]]+=lz[y];
    else rs[x]=merge(rs[x],rs[y]);
    lz[x]+=lz[y];
    return x;
  }
  int query(int x,int h,int t,int pos)
  {
    if (x==0) return 0;
    if (h==t) return lz[x];
    down(x);
    if (pos<=mid) return max(lz[x],query(ls[x],h,mid,pos));
    else return max(lz[x],query(rs[x],mid+1,t,pos));
  }
  void change(int &x,int h,int t,int h1,int t1,int k)
  {
    if (!x) x=++cnt;
    if (h1<=h&&t<=t1)
    { 
      lz[x]=max(lz[x],k);
      return;
    }
    down(x);
    if (h1<=mid) change(ls[x],h,mid,h1,t1,k);
    if (mid<t1) change(rs[x],mid+1,t,h1,t1,k);
  }
}se1;
void dfs(int x,int fa)
{
  int u=head[x];
  while (u)
  {
    int v=a[u].b;
    dfs(v,x);
    se1.rt[x]=se1.merge(se1.rt[x],se1.rt[v]);
    u=a[u].a;
  }
  se1.change(se1.rt[x],1,n,vv[x],n,se1.query(se1.rt[x],1,n,vv[x]-1)+1);
}
bool cmp(re x,re y)
{
  return(x.a<y.a);
}
int main()
{
 // freopen("1.in","r",stdin);
  //freopen("1.out","w",stdout);
  cin>>n;
  for (int i=1;i<=n;i++)
  {
    cin>>v[i].a>>fa[i];
    v[i].b=i;
    if (fa[i]) arr(fa[i],i);
  }
  sort(v+1,v+n+1,cmp);
  v[0].a=INF;
  int cnt=0;
  for (int i=1;i<=n;i++)
  {
    if (v[i].a!=v[i-1].a) cnt++;
    vv[v[i].b]=cnt;
  }
  dfs(1,0);
  int ans2=0;
  for(int i=1;i<=n;i++)
      ans2=max(ans2,se1.query(se1.rt[1],1,n,i));
  cout<<ans2;
  return 0;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *