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

题目分析

本题解时间复杂度$O(T\log n)$，标程$O(T{\log }^{2}n)$

• 发现每个节点的按顺序$build$产生的加法序列的规律：(若干个$1$)+(相同个数个$2,3,\mathrm{4...}$)+(若干个相同数字)，然后发现加$2,3,4,...$的次数与层节点个数有关。即为加$2^{\lfloor lo{g}_{2}x\rfloor }$次$2,3,4,\dots$。

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

• 那么我们可以写成式子：假设加法序列长度为$siz$，加$1$的个数为$cn{t}_1$，那么该节点$rt$的加和可以表示为：
  $$cn{t}_1+(\frac{(\frac{(siz-cnt1)}{(2^{\lfloor lo{g}_{2}x\rfloor })}+1)\times (\frac{(siz-cnt1)}{(2^{\lfloor lo{g}_{2}x\rfloor })}+2)}{2}-1)\times 2^{\lfloor lo{g}_{2}x\rfloor }+[(siz-cn{t}_1)\mathrm{mod}(2^{\lfloor lo{g}_{2}x\rfloor }))]\times (\frac{(siz-cnt1)}{(2^{\lfloor lo{g}_{2}x\rfloor })}+2)$$

• 加的数字个数$siz$的规律，对于当前节点$rt$：

  • $\lceil (rt-2^{\lfloor lo{g}_{2}rt\rfloor })/2\rceil \mathrm{mod}2==1,siz-=2^{\lfloor lo{g}_{2}rt\rfloor -2}$
  • $\lceil (rt-2^{\lfloor lo{g}_{2}rt\rfloor })/2\rceil \mathrm{mod}2==0,siz-=2^{\lfloor lo{g}_{2}rt\rfloor -1}$

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

• $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\{

  2(⌊log2x⌋−1), (x−2⌊log2x⌋+1)mod2=12⌊log2x⌋, (x−2⌊log2x⌋+1)mod2=0" role="presentation" style="position: relative;">2(⌊log2x⌋−1), (x−2⌊log2x⌋+1)mod2=12⌊log2x⌋, (x−2⌊log2x⌋+1)mod2=0$$\begin{array}{c}{2}^{(\lfloor lo{g}_{2}x\rfloor -1)},(x-2^{\lfloor lo{g}_{2}x\rfloor }+1)\mathrm{mod}2=1\\ 2^{\lfloor lo{g}_{2}x\rfloor },(x-2^{\lfloor lo{g}_{2}x\rfloor }+1)\mathrm{mod}2=0\end{array}$$
  \right. cnt1​={2(⌊log2​x⌋−1), (x−2⌊log2​x⌋+1)mod2=12⌊log2​x⌋, (x−2⌊log2​x⌋+1)mod2=0​

• 注意，当$siz<0$时，特判输出$0$，对第一层求$siz$时也要特判避免溢出。同时对$n=1$的$4$种情况也要特判，避免溢出。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;


inline void solve(){
    int n = 0, x = 0; cin >> n >> x;
    if(n == 1 && x == 1){ cout << 1 << endl; return; }
    else if(n == 1 && x != 1){ cout << 0 << endl; return; }
    if(x == 1){ cout << (n * (n + 1) / 2) << endl; return; }
    //cout << "FUCK:" << get_range(x) << endl;
    //if(x > get_range(x)){ cout << 0 << endl; return; }
    int ceng = log2(x), ceng_fir = (1 << (ceng));
    int cnt1 = ((x - ceng_fir + 1) % 2) ? (1 << (ceng - 1)) : ceng_fir;
    if((x - ceng_fir + 1) == 0) cnt1 = ceng_fir;
    // cnt_1 -> 1的个数
    int siz = n;
    int rt = x;
    while(rt != 2 && rt != 3){
        // cout << rt << " BEF | ";
        int ceng_now = log2(rt) + 1, ser = rt - (1 << (ceng_now - 1)) + 1;
        int md = ser % 4;
        if(md == 1 || md == 2) siz -= (1 << (ceng_now - 3));
        if(md == 3 || md == 0) siz -= (1 << (ceng_now - 2));
        rt >>= 1;
        // cout << rt << " AFT " << endl;
        // cout << siz << endl;
    }
    if(rt != 1) siz -= 1;
    if(siz <= 0){
        cout << 0 << endl;
        return;
    }
    if(siz <= cnt1){
        cout << siz << endl;
        return;
    }
    int yu = (siz - cnt1) % (ceng_fir), m = (siz - cnt1) / (ceng_fir);
    int ans = yu * (m + 2) + cnt1 + ceng_fir * ((m + 1) * (m + 2) / 2 - 1);
    cout << ans << endl;
}

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54