Difference between revisions of "Training 1: (Persistent) Segment Tree"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 1: | Line 1: | ||
== Problem A == | == Problem A == | ||
− | + | Solved by Weaver_zhu. | |
== Problem B == | == Problem B == |
Revision as of 12:20, 19 April 2019
Problem A
Solved by Weaver_zhu.
Problem B
Solved by Xiejiadong.
Problem form BZOJ1818.
题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。
题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。
于是就是求行和列两两之间的交点个数。
我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。
Problem C
Unsolved.
Problem D
Solved by Xiejiadong.
Problem from BZOJ3261.
可持久化字典树。
[题解]
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Unsolved.
Problem H
Unsolved.
Problem I
Unsolved.
Problem J
Unsolved.