首页 > 代码库 > [COGS 1535] [ZJOI2004]树的果实 树状数组+桶
[COGS 1535] [ZJOI2004]树的果实 树状数组+桶
我们用树状数组做差就可以解决一切问题,我用桶排并用此来表示出第几大就可以直接求前缀和了
#include<cstdio> #include<algorithm> #define MAXN 100010 using namespace std; inline int read() { int sum=0; char ch=getchar(); while(ch<‘0‘||ch>‘9‘)ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) { sum=(sum<<1)+(sum<<3)+ch-‘0‘; ch=getchar(); } return sum; } int P[MAXN],H[MAXN]; int n,m; struct VIA { int to,next; }c[MAXN]; int head[MAXN],t; inline void add(int x,int y) { c[++t].to=y; c[t].next=head[x]; head[x]=t; } inline int sum_H(int x) { int sum=0; while(x>0) sum+=H[x],x-=x&(-x); return sum; } inline int sum_P(int x) { int sum=0; while(x>0) sum+=P[x],x-=x&(-x); return sum; } inline void ins_P(int x,int key) { while(x<=n) P[x]+=key,x+=x&(-x); } inline void ins_H(int x,int key) { while(x<=n) H[x]+=key,x+=x&(-x); } int a[MAXN],pos[MAXN]; int Ans[MAXN][3]; int comp(const int x,const int y) { return a[x]>a[y]; } inline void Init() { scanf("%d",&n); for(int i=2,x;i<=n;i++)x=read(),add(x,i); for(int i=1;i<=n;i++)a[i]=read(),pos[i]=i; sort(pos+1,pos+n+1,comp); for(int i=1;i<=n;i++)a[pos[i]]=i; } void dfs(int x) { ins_H(a[x],1); int y=sum_H(a[x]-1); Ans[x][2]=sum_P(a[x]-1); ins_P(a[x],1); for(int i=head[x];i;i=c[i].next) dfs(c[i].to); Ans[x][1]=sum_H(a[x]-1)-y; ins_P(a[x],-1); Ans[x][0]=a[x]-1-Ans[x][1]; } inline void work() { dfs(1); for(int i=1;i<=n;i++) printf("%d %d %d\n",Ans[i][1],Ans[i][0],Ans[i][2]); } int main() { Init(); work(); return 0; }
[COGS 1535] [ZJOI2004]树的果实 树状数组+桶
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。