2Tree Queries (Çözgüdiň düşündirişi)

Solution

In the $2$Tree, node $u$ has children $2u$ and 2u+1. The depth is the number of edges to reach $1$, so

Hence all nodes of depth $y$ form the interval

We are given $n$ and queries (a,b,c,d), and we must count ordered pairs $(u,v)$ such that: 1\le u\le v\le n, $u$ is an ancestor of $v$, \mathrm{depth}(u)\in[a,b], \mathrm{depth}(v)\in[c,d].

Fix \mathrm{depth}(v)=y. Then $v$ has exactly one ancestor at each depth 0,1,\dots,y, so the number of ancestors $u$ with depth in $[a,b]$ equals the number of integers in

which is

All nodes $v$ of the same depth $y$ contribute the same $f(y)$, thus the query answer becomes

where $\mathrm{cnt}[y]$ is the number of nodes of depth $y$ among $[\mathrm{1..}n]$.

Let D=\lfloor \log_2 n \rfloor be the maximum depth. For 0\le y < D the level is full:

and the last level is partial:

For each query, if c>D the answer is $0$, and we clamp d=\min(d,D). Then we iterate y=c..d: let mx=\min(b,y), if mx\ge a add (mx-a+1)\cdot \mathrm{cnt}[y].

Since D\le 56 for n\le 10^{17}, each query is $O(D)$, i.e. about $57$ operations, which is fast for 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";
    }
}