在 dp 问题中,如果发现可以用后缀最大值来进行转移的话可以考虑去查分这个后缀最大值.

这样的话可以用差分的方式来方便地进行维护 ~

#include <bits/stdc++.h>
#define N 200007
#define ll long long
#define lson t[x].ls
#define rson t[x].rs
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int MM=1e7+5e6+20;
int edges,tot,n;
int hd[N],to[N<<1],nex[N<<1],rt[N],A[N],val[N];
struct node
{
int ls,rs,sum;
}t[MM];
inline int newnode() { return ++tot; }
inline void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
void update(int &x,int l,int r,int p,int v)
{
if(!x) x=newnode();
t[x].sum+=v;
if(l==r) return ;
int mid=(l+r)>>1;
if(p<=mid) update(lson,l,mid,p,v);
else update(rson,mid+1,r,p,v);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
int now=newnode();
t[now].sum=t[x].sum+t[y].sum;
t[now].ls=merge(t[x].ls,t[y].ls);
t[now].rs=merge(t[x].rs,t[y].rs);
return now;
}
int find(int x,int l,int r,int p)
{
if(!x) return 0;
if(l==r) return t[x].sum?l:0;
int mid=(l+r)>>1;
if(p<=mid)
{
return find(lson,l,mid,p);
}
else
{
int pp=find(rson,mid+1,r,p);
if(!pp) return find(lson,l,mid,p);
else return pp;
}
}
void dfs(int u,int ff)
{
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
dfs(v,u);
rt[u]=merge(rt[u],rt[v]);
}
update(rt[u],0,n,val[u],1);
int pos=find(rt[u],0,n,val[u]-1);
if(pos) update(rt[u],0,n,pos,-1);
}
int main()
{
// setIO("input");
int i,j;
scanf("%d",&n);
for(i=1;i<=n;++i) scanf("%d",&val[i]), A[i]=val[i];
sort(A+1,A+1+n);
for(i=1;i<=n;++i) val[i]=lower_bound(A+1,A+1+n,val[i])-A;
for(i=2;i<=n;++i)
{
int ff;
scanf("%d",&ff);
add(ff,i);
}
dfs(1,0);
printf("%d\n",t[rt[1]].sum);
return 0;
}

  

最新文章

  1. Swift enum(枚举)使用范例
  2. xcode8权限以及相关设置
  3. 在命令行中运行eclipse中创建的java项目
  4. Selenium2学习-009-WebUI自动化实战实例-007-Selenium 8种元素定位实战实例源代码(百度首页搜索录入框及登录链接)
  5. IO流 总结二
  6. C#的Timer
  7. 【python,logging】python中的logging模块
  8. DWZ(JUI) 教程 左侧栏默认是关闭状态的问题
  9. 《深入剖析Tomcat》阅读(三)
  10. Ubuntu ssh的使用
  11. C# 如何生成CHM帮助文件
  12. Linux(Cent OS7.2)下启动停止memcached方法及ps命令使用讲解
  13. Python禁用GC优化性能
  14. Leetcode——53.最大子序和
  15. DeepNetwork---tensorflow实现
  16. Sharing Configuration in ASP.NET Core SPA Scenarios
  17. 2. 集成学习(Ensemble Learning)Bagging
  18. 据库被标记为RESTORING的处理方式,正在还原中,正在恢复
  19. XPath轴
  20. PHP中imagecopyresampled参数详解

热门文章

  1. LeetCode第154场周赛(Java)
  2. Docker之dockerfile制作jdk镜像
  3. js 不同浏览器的类型判断 navigator.userAgent
  4. # - net - cannot access a disposed object r nobject name filebufferingreadstream
  5. java之spring mvc之Controller配置的几种方式
  6. 分页工具类PageResult
  7. 用vue-cli搭建vue项目
  8. JavaWeb 之 MVC 开发模式
  9. JVM粗解
  10. Spire.Doc 生成pdf业务运营报告