2022杭电多校 第6场 1008.Shinobu Loves Segment Tree 规律题

题目分析

本题解时间复杂度 O ( T log ⁡ n ) O(T\log n) O(Tlogn)，标程 O ( T log ⁡ 2 n ) O(T \log^2 n) O(Tlog2n)

• 发现每个节点的按顺序 b u i l d build build产生的加法序列的规律：(若干个 1 1 1)+(相同个数个 2 , 3 , 4... 2,3,4... 2,3,4...)+(若干个相同数字)，然后发现加 2 , 3 , 4 , . . . 2,3,4,... 2,3,4,...的次数与层节点个数有关。即为加 2 ⌊ l o g 2 x ⌋ 2^{{\lfloor log_2{x} \rfloor}} 2⌊log2​x⌋次 2 , 3 , 4 , … 2,3,4,\dots 2,3,4,…。

  这个规律可以通过 1. 1. 1.分析线段树 b u i l d build build性质 2. 2. 2.暴力打表(牛逼) 发现

• 那么我们可以写成式子：假设加法序列长度为 s i z siz siz，加 1 1 1的个数为 c n t 1 cnt_1 cnt1​，那么该节点 r t rt rt的加和可以表示为： c n t 1 + ( ( ( s i z − c n t 1 ) ( 2 ⌊ l o g 2 x ⌋ ) + 1 ) × ( ( s i z − c n t 1 ) ( 2 ⌊ l o g 2 x ⌋ ) + 2 ) 2 − 1 ) × 2 ⌊ l o g 2 x ⌋ + [ ( s i z − c n t 1 ) m o d    ( 2 ⌊ l o g 2 x ⌋ ) ) ] × ( ( s i z − c n t 1 ) ( 2 ⌊ l o g 2 x ⌋ ) + 2 ) cnt_1 + (\frac{(\frac{(siz - cnt1)}{(2^{{\lfloor log_2{x} \rfloor}})} + 1) \times (\frac{(siz - cnt1)}{(2^{{\lfloor log_2{x} \rfloor}})} + 2)}{2} - 1) \times 2^{{\lfloor log_2{x} \rfloor}} + [(siz - cnt_1) \mod (2^{{\lfloor log_2{x} \rfloor}}))] \times (\frac{(siz - cnt1)}{(2^{{\lfloor log_2{x} \rfloor}})} + 2) cnt1​+(2((2⌊log2​x⌋)(siz−cnt1)​+1)×((2⌊log2​x⌋)(siz−cnt1)​+2)​−1)×2⌊log2​x⌋+[(siz−cnt1​)mod(2⌊log2​x⌋))]×((2⌊log2​x⌋)(siz−cnt1)​+2)

• 加的数字个数 s i z siz siz的规律，对于当前节点 r t rt rt：

  • ⌈ ( r t − 2 ⌊ l o g 2 r t ⌋ ) / 2 ⌉ m o d    2 = = 1 , s i z − = 2 ⌊ l o g 2 r t ⌋ − 2 \lceil(rt - 2^{\lfloor log_2{rt} \rfloor}) / 2 \rceil \mod2 == 1, siz -= 2^{\lfloor log_2{rt} \rfloor - 2} ⌈(rt−2⌊log2​rt⌋)/2⌉mod2==1,siz−=2⌊log2​rt⌋−2
  • ⌈ ( r t − 2 ⌊ l o g 2 r t ⌋ ) / 2 ⌉ m o d    2 = = 0 , s i z − = 2 ⌊ l o g 2 r t ⌋ − 1 \lceil(rt - 2^{\lfloor log_2{rt} \rfloor}) / 2 \rceil \mod2 == 0, siz -= 2^{\lfloor log_2{rt} \rfloor - 1} ⌈(rt−2⌊log2​rt⌋)/2⌉mod2==0,siz−=2⌊log2​rt⌋−1

• 求 s i z siz siz时，可以令 s i z = n siz = n siz=n，然后沿着树上路径(实际上对应数字的二进制位)向上走，然后减去当前节点对应该减的值。

• 1 1 1的规律：可以 O ( 1 ) O(1) O(1)求： c n t 1 = { 2 ( ⌊ l o g 2 x ⌋ − 1 ) ,   ( x − 2 ⌊ l o g 2 x ⌋ + 1 ) m o d    2 = 1 2 ⌊ l o g 2 x ⌋ ,   ( x − 2 ⌊ l o g 2 x ⌋ + 1 ) m o d    2 = 0 cnt_1 =\left\{\begin{matrix} 2^{({\lfloor log_2{x} \rfloor} - 1)},\ (x - 2^{{\lfloor log_2{x} \rfloor}} + 1) \mod 2 =1 \\ 2^{{\lfloor log_2{x} \rfloor}},\ (x - 2^{{\lfloor log_2{x} \rfloor}} + 1) \mod 2 = 0 \end{matrix}\right. cnt1​={2(⌊log2​x⌋−1), (x−2⌊log2​x⌋+1)mod2=12⌊log2​x⌋, (x−2⌊log2​x⌋+1)mod2=0​

• 注意，当 s i z < 0 siz < 0 siz> n >> x; if(n == 1 && x == 1){ cout