luogu3605晋升者计数

https://www.zybuluo.com/ysner/note/1282069

题面

给一颗带点权的树，求每个点的子树中比该点权值大的点的个数。

\(n\leq10^5\)

解析

首先有个很无脑的方法。

用一个权值树状数组维护所有点权（离散化后的）。

每到一个点，询问比该点大的数的个数，然后把这个点权加入树状数组。

dfs回溯以后，再次询问，用这次答案减去上次答案。

这样可以在每个点上直接询问答案。

复杂度\(O(nlog^2n)\)。常数巨小。

然而我做这道题是想入门线段树合并。

其实思想正好相反。

我们不删点权，只把信息从下面合并上来。

对每个点，把它儿子的值域线段树与自己合并。

具体来说是从根节点出发，统计根结点的值，然后合并左儿子右儿子。

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define ll long long

#define re register

#define il inline

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=5e5+100,M=1e7;

struct Edge{int to,nxt;}e[N<<1];

int a[N],w[N],n,h[N],cnt,tot,ans[N],rt[M],s[M],ls[M],rs[M],tim;

il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

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

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

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

  return x*t;

}

il void Modify(re int &x,re int l,re int r,re int W)

{

  if(!x) x=++tim;

  ++s[x];

  if(l==r) return;

  re int mid=l+r>>1;

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

  return Modify(rs[x],mid+1,r,W);

}

il int Query(re int x,re int l,re int r,re int W)

{

  if(!x) return 0;

  if(l>=W) return s[x];

  re int mid=l+r>>1;

  if(W<=mid) return Query(ls[x],l,mid,W)+Query(rs[x],mid+1,r,W);

  return Query(rs[x],mid+1,r,W);

}

il int Merge(re int u,re int v)

{

  if(!u) return v;if(!v) return u;

  re int p=++tim;

  s[p]=s[u]+s[v];

  ls[p]=Merge(ls[u],ls[v]);

  rs[p]=Merge(rs[u],rs[v]);

  return p;

}

il void dfs(re int u)

{

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      dfs(v);

      rt[u]=Merge(rt[u],rt[v]);

    }

  ans[u]=Query(rt[u],1,tot,w[u]+1);

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

}

int main()

{

  memset(h,-1,sizeof(h));

  n=gi();

  fp(i,1,n) a[i]=w[i]=gi();

  fp(v,2,n)

    {

      re int u=gi();

      add(u,v);

    }

  sort(a+1,a+1+n);

  tot=unique(a+1,a+1+n)-a-1;

  fp(i,1,n) w[i]=lower_bound(a+1,a+1+tot,w[i])-a;

  dfs(1);

  fp(i,1,n) printf("%d\n",ans[i]);

  return 0;

}

巴特西

luogu3605晋升者计数

https://www.zybuluo.com/ysner/note/1282069

题面

解析

最新文章

热门文章