1.序列加强版
核心:
观察发现只会影响最后一列和每一行,不妨对每一个都建
立一颗平衡树维护序列(加点、删除,查询),但是不能
把每一个点都建立,否则空间会炸掉,并且观察到初始时
对于一段,他的编号都是连续的,每次出队也只会裂成两
段连续的点,因而可以考虑让平衡树上的每一个点都代表一段标号连续的区间,对于区间,只用记录左右编号
,同时,在split操作中,需要裂点,即将一个连续的区
间裂成两段区间。
骗分:
对于操作<=500中,可以考虑吧离散化并直接暴力模拟
对于x=1,可以直接建立两颗平衡树,维护第一行和最后一列
感想:
其实很多操作都是可以“一生二,二生三,三生万物”,比如在split中又是要分成很多段,但其实每次我只用将一分成两段,再继续分,最后还是可以达到目的,同时码量会小很多。
2.文文的摄影布置
收获点:
关于线段树要维护什么信息,可以总结出以下几点:
第一
题目问啥你就维护什么.
第二
维护的信息要有利于分治操作(服务于询问操作)