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

From EOJ Wiki
Jump to navigation Jump to search
 
(9 intermediate revisions by the same user not shown)
Line 2: Line 2:
  
 
Solved by Weaver_zhu.
 
Solved by Weaver_zhu.
 +
 +
Problem from HDU4578.
  
 
== Problem B ==
 
== Problem B ==
Line 19: Line 21:
 
== Problem C ==
 
== Problem C ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
Problem from SPOJCOT.
 +
 
 +
题意:求树链上 $k$ 大数。
 +
 
 +
树链剖分以后主席树维护即可。
  
 
== Problem D ==
 
== Problem D ==
Line 33: Line 41:
 
== Problem E ==
 
== Problem E ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
主席树。
 +
 
 +
[[http://xiejiadong.com/?p=2347 题解]]
  
 
== Problem F ==
 
== Problem F ==
Line 51: Line 63:
 
== Problem H ==
 
== Problem H ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
Problem from BZOJ3551.
 +
 
 +
主席树。
 +
 
 +
BZOJ3545和BZOJ3551题目一样,只不过3551要求强制在线。
 +
 
 +
因为我的做法BZOJ3545也是支持在线的,所以就无所谓了。
 +
 
 +
[[http://xiejiadong.com/?p=535 题解]]
  
 
== Problem I ==
 
== Problem I ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
Problem from Codeforces242E.
 +
 
 +
看到异或,考虑拆位。
 +
 
 +
维护 $20$ 棵线段树,对于每一位需要维护一个 tag 表示当前有没有置反,维护区间和即可。
  
 
== Problem J ==
 
== Problem J ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
Problem from POJ2777.
 +
 
 +
题意:支持两个操作:
 +
 
 +
* 给一个区间涂色
 +
* 询问一个区间里面有多少颜色
 +
 
 +
题解:颜色很少,状压。
 +
 
 +
线段树维护区间状态即可。
  
 
== Problem K ==
 
== Problem K ==
  
Unsolved.
+
Solved by Xiejiadong.
 +
 
 +
主席树。
 +
 
 +
求区间第$k$小数,权值线段树,差分维护。
 +
 
 +
在线段树上二分即可。

Latest revision as of 11:33, 14 September 2019

Problem A

Solved by Weaver_zhu.

Problem from HDU4578.

Problem B

Solved by Xiejiadong.

Problem form BZOJ1818.

题意:如果一个点位于四个黑点之间,那么他可以变成白点,求最后有多少个白点。

题解:对于行和列分别求出 max 和 min ,就可以得到行和列的作用域。

于是就是求行和列两两之间的交点个数。

我们用线段树维护列,用扫描线扫描行,遇到左端点的时候对那一列 +1 ,遇到右端点的时候,对那一列 -1 。每次询问一个区间和就行了。

Problem C

Solved by Xiejiadong.

Problem from SPOJCOT.

题意:求树链上 $k$ 大数。

树链剖分以后主席树维护即可。

Problem D

Solved by Xiejiadong.

Problem from BZOJ3261.

可持久化字典树。

[题解]

Problem E

Solved by Xiejiadong.

主席树。

[题解]

Problem F

Solved by Xiejiadong.

Problem from Codeforces1080F.

主席树。

[题解]

Problem G

Unsolved.

Problem H

Solved by Xiejiadong.

Problem from BZOJ3551.

主席树。

BZOJ3545和BZOJ3551题目一样,只不过3551要求强制在线。

因为我的做法BZOJ3545也是支持在线的,所以就无所谓了。

[题解]

Problem I

Solved by Xiejiadong.

Problem from Codeforces242E.

看到异或,考虑拆位。

维护 $20$ 棵线段树,对于每一位需要维护一个 tag 表示当前有没有置反,维护区间和即可。

Problem J

Solved by Xiejiadong.

Problem from POJ2777.

题意:支持两个操作:

  • 给一个区间涂色
  • 询问一个区间里面有多少颜色

题解:颜色很少,状压。

线段树维护区间状态即可。

Problem K

Solved by Xiejiadong.

主席树。

求区间第$k$小数,权值线段树,差分维护。

在线段树上二分即可。