本题单里的题目,由简单到难,逐渐递进,适合新学线段树 or 还只会打线段树板子选手。
P.S. 其中一些题目线段树并不是最好的办法,但线段树一定是可以过的
这部分都是线段树模板,切掉这些题,开始练习线段树吧:
- P3372 【模板】线段树 1
- P2068 统计和
- P1531 I Hate It
- P3373 【模板】线段树 2
这部分开始就不是简单的模板了,需要选手根据题目在线段树中维护一些东西:
- P2880 [USACO07JAN]Balanced Lineup G
- P5057 [CQOI2006]简单题
- P3870 [TJOI2009]开关
- P1816 忠诚
- P1083 [NOIP2012 提高组] 借教室
这部分就需要好好思考题目了,不像上个部分,需要维护的东西和做法并不是显而易见的,有时还需要结合一些数学知识:
- P1438 无聊的数列
- P1471 方差
- P4145 上帝造题的七分钟2 / 花神游历各国
- P2184 贪婪大陆
- P5568 [SDOI2008]校门外的区间
- P4314 CPU监控
- P2572 [SCOI2010]序列操作
非常经典的GSS系列,如果切掉这部分,那绝对就是线段树大神了:
- SP1043 GSS1 - Can you answer these queries I
- SP1557 GSS2 - Can you answer these queries II
- SP1716 GSS3 - Can you answer these queries III
- SP2713 GSS4 - Can you answer these queries IV
- SP2916 GSS5 - Can you answer these queries V
- SP6779 GSS7 - Can you answer these queries VII