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)$求：
  $$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$，对第一层求$siz$时也要特判避免溢出。同时对$n=1$的$4$种情况也要特判，避免溢出。

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;
}