[关闭]
@ysner 2018-09-28T10:01:40.000000Z 字数 1754 阅读 1803

luogu3605晋升者计数

线段树合并 树状数组


题面

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

解析

首先有个很无脑的方法。
用一个权值树状数组维护所有点权(离散化后的)。
每到一个点,询问比该点大的数的个数,然后把这个点权加入树状数组。
dfs回溯以后,再次询问,用这次答案减去上次答案。
这样可以在每个点上直接询问答案。
复杂度。常数巨小。

然而我做这道题是想入门线段树合并。
其实思想正好相反。
我们不删点权,只把信息从下面合并上来。
对每个点,把它儿子的值域线段树与自己合并。
具体来说是从根节点出发,统计根结点的值,然后合并左儿子右儿子。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=5e5+100,M=1e7;
  14. struct Edge{int to,nxt;}e[N<<1];
  15. int a[N],w[N],n,h[N],cnt,tot,ans[N],rt[M],s[M],ls[M],rs[M],tim;
  16. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  17. il ll gi()
  18. {
  19. re ll x=0,t=1;
  20. re char ch=getchar();
  21. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  22. if(ch=='-') t=-1,ch=getchar();
  23. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  24. return x*t;
  25. }
  26. il void Modify(re int &x,re int l,re int r,re int W)
  27. {
  28. if(!x) x=++tim;
  29. ++s[x];
  30. if(l==r) return;
  31. re int mid=l+r>>1;
  32. if(W<=mid) return Modify(ls[x],l,mid,W);
  33. return Modify(rs[x],mid+1,r,W);
  34. }
  35. il int Query(re int x,re int l,re int r,re int W)
  36. {
  37. if(!x) return 0;
  38. if(l>=W) return s[x];
  39. re int mid=l+r>>1;
  40. if(W<=mid) return Query(ls[x],l,mid,W)+Query(rs[x],mid+1,r,W);
  41. return Query(rs[x],mid+1,r,W);
  42. }
  43. il int Merge(re int u,re int v)
  44. {
  45. if(!u) return v;if(!v) return u;
  46. re int p=++tim;
  47. s[p]=s[u]+s[v];
  48. ls[p]=Merge(ls[u],ls[v]);
  49. rs[p]=Merge(rs[u],rs[v]);
  50. return p;
  51. }
  52. il void dfs(re int u)
  53. {
  54. for(re int i=h[u];i+1;i=e[i].nxt)
  55. {
  56. re int v=e[i].to;
  57. dfs(v);
  58. rt[u]=Merge(rt[u],rt[v]);
  59. }
  60. ans[u]=Query(rt[u],1,tot,w[u]+1);
  61. Modify(rt[u],1,tot,w[u]);
  62. }
  63. int main()
  64. {
  65. memset(h,-1,sizeof(h));
  66. n=gi();
  67. fp(i,1,n) a[i]=w[i]=gi();
  68. fp(v,2,n)
  69. {
  70. re int u=gi();
  71. add(u,v);
  72. }
  73. sort(a+1,a+1+n);
  74. tot=unique(a+1,a+1+n)-a-1;
  75. fp(i,1,n) w[i]=lower_bound(a+1,a+1+tot,w[i])-a;
  76. dfs(1);
  77. fp(i,1,n) printf("%d\n",ans[i]);
  78. return 0;
  79. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注