2Tree Запити#12314

2Tree Запити (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

У $2$ Tree, вузол $u$ має нащадків $2 u$ та $2 u + 1$ 2u+1. Глибина — це кількість ребер, щоб досягти $1$ , тому

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

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

Отже, всі вузли глибини $y$ формують інтервал

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

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

Нам дано $n$ та запити $(a, b, c, d)$ (a,b,c,d), і ми повинні підрахувати впорядковані пари $(u, v)$ такі, що: $1 \leq u \leq v \leq n$ 1\le u\le v\le n, $u$ є предком $v$ , $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. Тоді $v$ має точно одного предка на кожній глибині $0, 1, \dots, y$ 0,1,\dots,y, тому кількість предків $u$ з глибиною в $[a, b]$ дорівнює кількості цілих чисел в

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

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

що дорівнює

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

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

Всі вузли $v$ однієї й тієї ж глибини $y$ вносять однакове $f (y)$ , отже, відповідь на запит стає

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

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

де $cnt [y]$ — це кількість вузлів глибини $y$ серед $[1.. n]$ .

Нехай $D = ⌊ lo g_{2} n ⌋$ D=\lfloor \log_2 n \rfloor буде максимальною глибиною. Для $0 \leq y < D$ 0\le y < D рівень заповнений:

cnt [y] = 2^{y},

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

а останній рівень частковий:

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

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

Для кожного запиту, якщо $c > D$ c>D, відповідь дорівнює $0$ , і ми обмежуємо $d = min (d, D)$ d=\min(d,D). Потім ми ітеруємо $y = c .. d$ y=c..d: нехай $m x = min (b, y)$ mx=\min(b,y), якщо $m x \geq a$ mx\ge a, додаємо $(m x - a + 1) \cdot cnt [y]$ (mx-a+1)\cdot \mathrm{cnt}[y].

Оскільки $D \leq 56$ D\le 56 для $n \leq 1 0^{17}$ n\le 10^{17}, кожен запит є $O (D)$ , тобто близько $57$ операцій, що швидко для $q \leq 1 0^{6}$ q\le 10^6.

#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++