T1、序列操作
http://blog.csdn.net/willinglive/article/details/37921297
1.两个lazy标记时,不能同时存在,pushdown中要消
2.任何询问调用pushdown保证L<=R!!!
3.pushdown尽量不要写在前面(这样我从来就没调对过),lazy表示当前节点已经修改
T2、wikioi 行星序列
1.对lazy操作的进一步理解,与T1不同,两个lazy可以同时存在(此题彻底颠覆了对lazy的理解),lazy的合并操作
2.注意k和b可以取模,k和b的合并要细心
T3、tyvj 小白逛公园
http://blog.csdn.net/willinglive/article/details/38065327
线段树合并的更深一步的理解,改代码完全不用担心询问操作跨越左右儿子区间的询问问题
这个代码是错的:
maxs:最大子区间和
maxs[p]=max(maxs[l],maxs[r]);
maxs[p]=max(maxs[p],max(maxr[l],0)+max(maxl[r]),0));
问什么呢?这个问题早在“序列操作”一题中就遇到过,询问可能跨越了左右儿子,不过“序列操作”太巧了,刚好能解决,不过这个题不行了
这个代码的巧妙之处就在于完全不用担心序列的合并问题,因为询问操作函数的类型是一个线段,合并的也是线段
这就更体现了线段树的实质
也就是说线段树左右儿子的全包含合并能实现,但半包含合并不能实现时,可以用这个方法了
不过这样的话只能用struct了,牺牲了点速度
目测不影响lazy
线段树不能实现的:
1.翻转区间(平衡树)
2.统计区间大于k的个数(特别小的范围可以手动,比较小的范围用二位BIT或者SegTree)
3.区间开方(见上帝一题)