关于划分树的一些感想(以及我洗心革面之后的划分树)

首先是听从了TLK同学的意见, 在建树之前先离散化, 省得每次都要用常数较大的快速选择(虽然依旧是线性)来找中位数(这种做法的其他诸多弊端包括要判重),果然常数小了不少

然后是苦苦挣扎(Orz)的区间转移(特别是转到右子树), 若当前区间是[L,R]

  1. 转移到左子树: L处元素之前有 X=L?toLeft[L-1]:0 个元素进入了左子树, 所以之前元素的下标是 X-1 , 所以L的新下标是 X-1+1=X. 但是!如果L之前没有元素进入左子树( 也就是X=0), 那么L的新下标应该是0, 因为应该从头开始在左子树里面搜索(说不清,自己感受). 因此并不是 1+(L?toLeft[L-1]:0), 而是 L?toLeft[L-1]-1+1:0
  2. 转移到右子树: 对于N处的元素, toRight[N]是不是等于 N-toLeft[N]? 不是! 因为数组下标是零开始, 所以到N的时候实际上已经有N+1个元素了Orz( 在这里卡了好久), 因此应该是 toRight[N]=N+1-toLeft[N], 有了toRight以后别的细节参考左子树

BSOJ的TLE耻辱截图QAQ

BSOJ划分树TLEBSOJ划分树的耻辱

感情我是唯一一个没有AC的咯捂脸熊流泪

(和标题说好的不一样,此处并没有划分树)