Difference between revisions of "Training 1: (Persistent) Segment Tree"

From EOJ Wiki
Jump to navigation Jump to search
Line 37: Line 37:
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
Problem from Codeforces1080F.
 +
 
 +
主席树。
 +
 
 +
[[http://xiejiadong.com/?p=531 题解]]
  
 
== Problem G ==
 
== Problem G ==

Revision as of 14:50, 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

Solved by Xiejiadong.

Problem from Codeforces1080F.

主席树。

[题解]

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.