生活随笔
收集整理的這篇文章主要介紹了
P3605 [USACO17JAN]Promotion Counting P（树状数组）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
解析
做法很多的一道題
sol1
先求出dfs序，離線下來，然后按權(quán)值大小的順序統(tǒng)計答案并插到對應(yīng)的dfs序中
sol2
離散化后，dfs過程中動態(tài)維護(hù)樹狀數(shù)組，利用前后差值求出答案
sol3
樹上dsu
就比較無腦了，暴力維護(hù)即可
但是代碼比前兩個難寫
sol4
權(quán)值線段樹合并
這個做法在本題中確實是一點優(yōu)勢也沒有
兼具了常數(shù)大和難編寫的雙重優(yōu)勢（bushi
總的來說，前兩種做法比較推薦
代碼
使用的是soltion1
別問我為什么當(dāng)時還敲了個樹剖和線段樹上去
#include<bits/stdc++.h>
using namespace std
;
#define ll long long
const int N
=3e5+100;
int n
,m
;
struct node{int to
,nxt
;
}p
[N
<<1];
int fi
[N
],cnt
=-1;
void addline(int x
,int y
){p
[++cnt
]=(node
){y
,fi
[x
]};fi
[x
]=cnt
;
}
int dfn
[N
],fa
[N
],top
[N
],pos
[N
],tim
,dep
[N
],hson
[N
],siz
[N
];
void dfs1(int x
,int f
){fa
[x
]=f
;siz
[x
]=1;for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==f
) continue;dep
[to
]=dep
[x
]+1;dfs1(to
,x
);siz
[x
]+=siz
[to
];if(!hson
[x
]||siz
[hson
[x
]]<siz
[to
]) hson
[x
]=to
;}return;
}
void dfs2(int x
,int tp
){dfn
[++tim
]=x
;pos
[x
]=tim
;top
[x
]=tp
;if(hson
[x
]) dfs2(hson
[x
],tp
);for(int i
=fi
[x
];~i
;i
=p
[i
].nxt
){int to
=p
[i
].to
;if(to
==fa
[x
]||to
==hson
[x
]) continue;dfs2(to
,to
);}return;
}
#define mid ((l+r)>>1)
#define ls k<<1
#define rs k<<1|1
ll sum
[N
<<2],add
[N
<<2];
void pushup(int k
){sum
[k
]=sum
[ls
]+sum
[rs
];
}
void Add(int k
,int l
,int r
,ll v
){add
[k
]+=v
;sum
[k
]+=1ll*(r
-l
+1)*v
;return;
}
void pushdown(int k
,int l
,int r
){ll o
=add
[k
];add
[k
]=0;if(!o
) return;Add(ls
,l
,mid
,o
);Add(rs
,mid
+1,r
,o
);return;
}
void change(int k
,int l
,int r
,int x
,int v
){if(l
==r
){sum
[k
]+=v
;return;}pushdown(k
,l
,r
);if(x
<=mid
) change(ls
,l
,mid
,x
,v
);else change(rs
,mid
+1,r
,x
,v
);pushup(k
);return;
}
void longchange(int k
,int l
,int r
,int x
,int y
,int v
){if(x
<=l
&&r
<=y
){Add(k
,l
,r
,v
);return;}pushdown(k
,l
,r
);if(x
<=mid
) longchange(ls
,l
,mid
,x
,y
,v
);if(y
>mid
) longchange(rs
,mid
+1,r
,x
,y
,v
);pushup(k
);return;
}
ll
ask(int k
,int l
,int r
,int x
,int y
){if(x
<=l
&&r
<=y
){return sum
[k
];}pushdown(k
,l
,r
);ll res
=0;if(x
<=mid
) res
+=ask(ls
,l
,mid
,x
,y
);if(y
>mid
) res
+=ask(rs
,mid
+1,r
,x
,y
);return res
;
}
ll
sumquery(int x
,int y
){ll res
=0;while(top
[x
]!=top
[y
]){if(dep
[top
[x
]]<dep
[top
[y
]]) swap(x
,y
);res
+=ask(1,1,n
,pos
[top
[x
]],pos
[x
]);x
=fa
[top
[x
]];}if(dep
[x
]<dep
[y
]) swap(x
,y
);res
+=ask(1,1,n
,pos
[y
],pos
[x
]);return res
;
}
struct P{int id
,v
;bool operator < (const P y
)const{return v
>y
.v
;}
}a
[N
];
int ans
[N
];
int main(){memset(fi
,-1,sizeof(fi
));scanf("%d",&n
);for(int i
=1;i
<=n
;i
++){scanf("%d",&a
[i
].v
);a
[i
].id
=i
;}int x
,y
;for(int i
=2;i
<=n
;i
++){scanf("%d",&x
);addline(x
,i
);addline(i
,x
);}dfs1(1,0);dfs2(1,1);sort(a
+1,a
+1+n
);for(int i
=1;i
<=n
;i
++){int now
=a
[i
].id
;ans
[now
]=ask(1,1,n
,pos
[now
],pos
[now
]+siz
[now
]-1);change(1,1,n
,pos
[now
],1);}for(int i
=1;i
<=n
;i
++) printf("%d\n",ans
[i
]);
}
總結(jié)
以上是生活随笔為你收集整理的P3605 [USACO17JAN]Promotion Counting P（树状数组）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
