2Tree Sorğuları#12314

2Tree Sorğuları (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

$2$ Tree-də, $u$ düyünü $2 u$ və $2 u + 1$ 2u+1 uşaqlarına malikdir. Dərinlik $1$ -ə çatmaq üçün kənarların sayıdır, belə ki

depth (x) = ⌊ lo g_{2} x ⌋ .

\mathrm{depth}(x)=\lfloor \log_2 x \rfloor.

Beləliklə, dərinliyi $y$ olan bütün düyünlər aşağıdakı intervalları təşkil edir:

[2^{y}, 2^{y + 1} - 1] .

[2^y,\;2^{y+1}-1].

Bizə $n$ və $(a, b, c, d)$ (a,b,c,d) sorğuları verilib, və biz $(u, v)$ sıralı cütlərini saymalıyıq ki: $1 \leq u \leq v \leq n$ 1\le u\le v\le n, $u$ $v$ -nin atasıdır, $depth (u) \in [a, b]$ \mathrm{depth}(u)\in[a,b], $depth (v) \in [c, d]$ \mathrm{depth}(v)\in[c,d].

$depth (v) = y$ \mathrm{depth}(v)=y sabitləşdirin. Onda $v$ -nin hər dərinlikdə $0, 1, \dots, y$ 0,1,\dots,y tam bir atası var, beləliklə $[a, b]$ intervalında dərinliyi olan ataların $u$ sayı

[a, b] \cap [0, y]

[a,b]\cap[0,y]

bərabərdir

f (y) = max (0, min (b, y) - a + 1) .

f(y)=\max\bigl(0,\;\min(b,y)-a+1\bigr).

Eyni dərinlik $y$ olan bütün $v$ düyünləri eyni $f (y)$ -ni töhfə verir, beləliklə sorğunun cavabı

y = c \sum d cnt [y] \cdot f (y),

\sum_{y=c}^{d} \mathrm{cnt}[y]\cdot f(y),

burada $cnt [y]$ $[1.. n]$ arasında dərinliyi $y$ olan düyünlərin sayıdır.

$D = ⌊ lo g_{2} n ⌋$ D=\lfloor \log_2 n \rfloor maksimum dərinlikdir. $0 \leq y < D$ 0\le y < D üçün səviyyə tamdır:

cnt [y] = 2^{y},

\mathrm{cnt}[y]=2^y,

və son səviyyə qismidir:

cnt [D] = n - 2^{D} + 1.

\mathrm{cnt}[D]=n-2^D+1.

Hər bir sorğu üçün, əgər $c > D$ c>D cavab $0$ -dır, və $d = min (d, D)$ d=\min(d,D)-ni sıxırıq. Sonra $y = c .. d$ y=c..d arasında iterasiya edirik: $m x = min (b, y)$ mx=\min(b,y) qoyun, əgər $m x \geq a$ mx\ge a isə $(m x - a + 1) \cdot cnt [y]$ (mx-a+1)\cdot \mathrm{cnt}[y] əlavə edin.

$D \leq 56$ D\le 56 olduğu üçün $n \leq 1 0^{17}$ n\le 10^{17}, hər bir sorğu $O (D)$ -dir, yəni təxminən $57$ əməliyyat, bu da $q \leq 1 0^{6}$ q\le 10^6 üçün sürətlidir.

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n; int q;
    cin>>n>>q;

    int D=63-__builtin_clzll((unsigned long long)n);

    vector<long long> cnt(D+1);
    for(int y=0;y<D;y++)cnt[y]=1LL<<y;
    cnt[D]=n-(1LL<<D)+1;

    while(q--){
        long long a,b,c,d;
        cin>>a>>b>>c>>d;

        if(c>D){cout<<0<<"\n";continue;}
        if(d>D)d=D;

        long long ans=0;
        for(long long y=c;y<=d;y++){
            long long mx=min(b,y);
            if(mx>=a)ans+=(mx-a+1)*cnt[y];
        }
        cout<<ans<<"\n";
    }
}

C++