2022 Hangzhou Electric Power Multi-School Session 6 1008.Shinobu Loves Segment Tree Regular Questions

题目分析

The time complexity of solving this problem$O(T\log n)$,标程$O(T{\log }^{2}n)$

• Find each node in order$build$The regularity of the resulting addition sequence：(若干个$1$)+(same number$2,3,\mathrm{4...}$)+(several identical numbers),Then find the plus$2,3,4,...$The number of times is related to the number of layer nodes.即为加$2^{\lfloor lo{g}_{2}x\rfloor }$次$2,3,4,\dots$.

  This rule can be passed$1.$Analyze the segment tree$build$性质 $2.$暴力打表(牛逼) 发现

• Then we can write the formula：Suppose the addition sequence length is $siz$,加$1$的个数为$cn{t}_1$,那么该节点$rt$The sum of can be expressed as ：
  $$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)$$

• The number of digits to add$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$,Then follow the path up the tree(Actually corresponds to the binary digit of the number)向上走,Then subtract the value corresponding to the current node.

• $1$的规律：可以$O(1)$求：
  $$cn{t}_1=\{\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}$$

• 注意,当$siz<0$时,特判输出$0$,Ask for the first level$siz$It is also necessary to make special judgments to avoid overflow.同时对$n=1$的$4$A special case is also required,避免溢出.

Code

#include <bits/stdc++.h>
#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;
}