这是DSA 2023 Spring PA 3的Kidd的解题报告，内容涉及线段树。特别地，这篇文章讲述了如何解决九成测最后3个测试点Wrong Answer的问题。
A.所使用数据结构与算法的构思、原理和实现要点
所使用的数据结构：
线段树：输入的所有区间排序去重后得到最小区间，每个最小区间相当于一个线段树的叶子结点，以此构建线段树。
算法构思：
1 在输入后，将所有端点值排序去重，得到所有的最小区间
2 将输入的数据导入代表线段树的数组，充当叶子结点
3 从0开始，递归地建立线段树的非叶子节点。在这一过程中，同时把线段树用0补全成一棵完全二叉树。
4 按输入顺序执行反转和查询操作。具体来说，两个操作都从根节点开始，以递归的形式执行，将区间逐渐限制到指定的区间。
5 反转操作中，当传入的目标区间和当前节点区间等大，只增加懒惰标记；当传入的目标区间被包含于当前节点区间，计算当前节点的新增反转次数；之后，继续递归，如果在当前节点所代表区间的左半部分有目标区间，则继续向下方左孩子标记，右半部分同理。
6 查询操作中，如果当前节点有懒惰标记，则立刻将其下推给子节点；如果已经进入叶子结点，计算当前节点新增翻转次数并计入；如果传入的目标区间和当前节点区间等大，则将当前节点翻转次数计入，不向下查询；否则就继续向子节点递归。
实现要点：
1 使用定长的结构体数组存放树的信息，每个点的信息由一个结构体对象承载。
2 懒惰标记及时清零，不重复记录。
3 查询时，不要每一次碰到懒惰标记都直接下推到叶子节点，否则会超时。实际上，只需要下推一层。因为如果需要这个节点子节点的数据的话，查询函数会递归进入子节点，自然会继续将需要的懒惰标记继续下推，而不需要的懒惰标记不用继续下推。
4 输入数据时，每个区间的右端点自动加1，把每个区间都变成左闭右开区间，这样做有两个好处：1 当查询一个点时，可以避免这个点的两个端点在去重时变成一个，进而导致没有建立只含该店的区间节点，最终导致查询结果偏大；2 在从小到大排序后，最后一个端点一定是加1之后产生的，因此所有端点都是左闭右开的，完全一致，不需要特别判定。
B.完成过程中遇到的问题，排除问题的主要过程、使用的方法和技巧，以及参考资料
问题1：五成测有些测试点出现错误
经过对拍构造错误和调试分析，发现是因为有些节点的懒惰标记未被计入祖先节点的翻转次数，所以加入了“当传入的目标区间被包含于当前节点区间，计算当前节点的新增反转次数”。
问题2：九成测最后三个测试点 Wrong Answer
考虑到九成测最后三个数据点数据量一般较大，且如果数组越界访问到其他数组并不一定会报出 Runtime Error 错误，所以认为还是有一些数组存在越界情况。最终发现，是因为：补全成完全二叉树的过程中，叶子结点会被用0补全到比区间数目更大的第一个2的幂。对于200000（这是数据范围上限）个区间来说，400000个位置的数组是不够的表示线段树的。因此，我加大了线段树数组的大小。
参考资料
除了习题课PPT，没有参考其他资料。
C.时间和空间复杂度的估算
时间复杂度
每次操作的时间复杂度为O(logm)，考虑到一共有m次反转和查询操作，总体时间复杂度为O(mlogm)。m为题目描述中的m，即操作次数。
空间复杂度
使用的是定长数组，所以占用的空间是定值。在这些空间中，实际使用的空间是O(m)，m为题目描述中的m。这是因为所有的数据都只存储了常数次。