树状数组求逆序对【模板】

存板子

0

[JZOJ4747]被粉碎的线段树

Problem

相信你已经对线段树有所了解,但是小R的线段树没学好。于是他的线段树就有显得有些竒怪了。他的线段树与传统线段树的唯一区别如下:
传统线段树非叶子节点的划分点\( \text{mid} = \left \lfloor \dfrac{l + r}{2}\right \rfloor\)但小R线段树的划分点\(\text{mid}\)是自己定的但满足\( l \leq \text{mid} \leq r\),其余条件同原来线段树。那么不难发现如下性质:
1.该线段树的节点个数依然为\( 2N – 1\)
2.该线段树深度可能会超过\( O(\log n)\)
3.该线段树区间定位所包含的线段树节点个数可能超过\( O(\log n)\)。但区间定位的结果依然是唯一的。
小R给你这样一个小R线段树,每次询问给定区间的区间定位个教。

继续阅读 [JZOJ4747]被粉碎的线段树

0