1. 所使用数据结构与算法的构思、原理和
实现要点。
数据结构
采用线段树储存 n 张牌:
线段树的每个节点的数据元素:(覆盖范围为[down,up])
down,up,覆盖的这段范围有几个为 1 的数 count,有几次反转没传递下去
nopass(nopass=0 或 1)
用指针 le 和 right 指向左右孩子
思路
H 操作:
从 根 节 点 开 始 遍 历 , 反 转 覆 盖 i 到 j 的 最 高 的 树 ( count=up-down+1-
count;nopass=(!nopass))。
Q 操作:
从根节点开始遍历,查找覆盖 i 至 j 最高的树,每经过一个节点,如果
nopass=1,子节点反转(count= up-down+1-count;nopass=(!nopass)),该节