好题，我懂得欣赏。

首先找个办法算答案，记 $X$ 等于你最终的 $x$，显然你只关心这个。然后发现对于每个 $l \leq i \leq r$ 必须要有 $b_i$ 二进制下最高非 $0$ 位不超过 $X$ 二进制下非 $0$ 最高位，然后你发现，一个 $b_i$ 的贡献只与 $b_i,X$ 的大小关系有关，具体而言 $b_i \leq X$ 则需要一次否则需要两次。

记 $S$ 表示所有二进制下非 $0$ 最高位与 $X$ 相同的数构成的可重集，去掉一些无关紧要的常数项，实际上你要最优化的东西就是 $\min_{c=2^h}^{2^{h+1}-1}(c+\sum_{x \in S} [x>c])$。

这个形式很烂，考虑转换一下，首先对于每个数按照二进制下最高非 $0$ 位分层，每一层把最高位减掉，式子变成 $\min_{c=0}^{\infty} (c+\sum_{x \in S} [x>c])$。

依然不好处理，考虑一个看似没啥用的处理，把 $\min$ 变成 $\max$，也就是我们考虑从 $c=0$ 的状态出发，通过调整 $c$ 最多能省下多少贡献，也就是要求出 $\max_{c=0}^{\infty}(\sum_{x \in S} [x \leq c] - c)$。

考虑一个很厉害的转换，注意到式子是 Hall 定理的形式，考虑逆着用一下，构造左右两排点，左边是 $S$ 内所有数，右边是 $1$ 到正无穷所有数，左边每个 $x$ 向右边所有不超过其的位置连边，则式子 $\max_{c=0}^{\infty}(\sum_{x \in S} [x \leq c] - c)$ 的含义就是最大匹配下左边有多少个点失配了。

注意到，这个匹配形式非常好，左部点的邻域是一个前缀，我们声称：可以以任意顺序增广，并且不反悔的前提下求出最大匹配。

证明考虑反悔形如：原来 $x$ 匹配 $y$，然后令 $z$ 匹配 $y$ 并让 $x$ 匹配一个比 $z$ 更大的元素 $w$，所以如果我一开始就让每个 $x$ 在加入时匹配能匹配的最大元素，后面就不会有反悔空间，也就不需要反悔了。

至此我们得到了足够强的结论了，开始做原问题。考虑扫描线。扫描右端点，当你扫描到 $r$ 时，考虑对于每个 $l$ 而言左部点失配了多少。直接做看似不好做，但是注意到前面我们分析出可以以任意顺序增广，考虑对于一个区间以 $r \to l$ 的顺序增广，如果我们已经处理出了从 $r-1$ 出发的情形，那么变成从 $r$ 出发后，唯一的变化（增量）就是可能会使得后面某一个从 $r-1$ 出发时没有失配的左部点 $u$ 被失配，同时让 $r$ 加入匹配中，那么只要我们能找到这个 $u$，就可以维护答案（答案的增量是 $l \leq u$ 的位置失配点数量加 $1$）。

考虑怎么找出这个 $u$，再考虑 Hall 定理一下，令 $b_i = \sum_{x \in S} i - [x \leq i]$，那么集合 $S$ 中左部点是一个匹配的充要条件就是所有 $b_i \geq 0$。找出 $u$ 就考虑加入 $r$ 的影响，也就是令 $i \in [a_r,\infty]$ 的 $b_i \gets b_i - 1$ 后是否会有负数，如果有找到第一个负数位置 $p$，我们需要撤销掉前面的左部点集合 $S$ 中最靠前的一次影响到 $p$ 位置的左部点，然后再将 $r$ 加入 $S$。不难发现以上所有操作都可以通过线段树维护出来，至于强制在线考虑主席树即可。再注意到有用的 $b_i$ 的下标是 $O(n)$ 的即可做到时间复杂度 $O((n+q) \log n)$。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
const int top = 2e5+14;
pair<int,int> tr[maxn<<2];
int tag[maxn<<2];
void pushup(int cur){
    tr[cur]=min(tr[cur<<1],tr[cur<<1|1]);
}
void pushdown(int cur){
    if(tag[cur]!=0){
        tr[cur<<1].first+=tag[cur];
        tag[cur<<1]+=tag[cur];
        tr[cur<<1|1].first+=tag[cur];
        tag[cur<<1|1]+=tag[cur];
        tag[cur]=0;
    }
}
void build(int cur,int lt,int rt){
    tag[cur]=0;
    if(lt==rt){
        tr[cur]={lt,lt};
        return ;
    }
    int mid=(lt+rt)>>1;
    build(cur<<1,lt,mid);
    build(cur<<1|1,mid+1,rt);
    pushup(cur);
}
void add(int cur,int lt,int rt,int l,int r,int c){
    if(rt<l||r<lt) return ;
    if(l<=lt&&rt<=r){
        tr[cur].first+=c;
        tag[cur]+=c;
        return ;
    }
    pushdown(cur);
    int mid=(lt+rt)>>1;
    add(cur<<1,lt,mid,l,r,c);
    add(cur<<1|1,mid+1,rt,l,r,c);
    pushup(cur);
}
pair<int,int> query(int cur,int lt,int rt,int l,int r){
    if(rt<l||r<lt) return {1e9,1e9};
    if(l<=lt&&rt<=r) return tr[cur];
    pushdown(cur);
    int mid=(lt+rt)>>1;
    return min(query(cur<<1,lt,mid,l,r),query(cur<<1|1,mid+1,rt,l,r));
}
int len;
vector<long long> A[60];
set<int> pos[60];
int rk[maxn];
set<int> S[maxn];
int Tr[maxn<<2];
void Pushup(int cur){
    Tr[cur]=min(Tr[cur<<1],Tr[cur<<1|1]);
}
void Build(int cur,int lt,int rt){
    Tr[cur]=1e9;
    if(lt==rt){
        S[lt].clear();
        return ;
    }
    int mid=(lt+rt)>>1;
    Build(cur<<1,lt,mid);
    Build(cur<<1|1,mid+1,rt);
    Pushup(cur);
}
void Ins(int cur,int lt,int rt,int pos,int c){
    if(lt==rt){
        S[lt].insert(c);
        Tr[cur]=(*S[lt].begin());
        return ;
    }   
    int mid=(lt+rt)>>1;
    if(pos<=mid) Ins(cur<<1,lt,mid,pos,c);
    else Ins(cur<<1|1,mid+1,rt,pos,c);
    Pushup(cur);
}
void Del(int cur,int lt,int rt,int pos,int c){
    if(lt==rt){
        S[lt].erase(c);
        Tr[cur]=(S[lt].size()==0?1e9:(*S[lt].begin()));
        return ;
    }   
    int mid=(lt+rt)>>1;
    if(pos<=mid) Del(cur<<1,lt,mid,pos,c);
    else Del(cur<<1|1,mid+1,rt,pos,c);
    Pushup(cur);
}
int Query(int cur,int lt,int rt,int l,int r){
    if(rt<l||r<lt) return 1e9;
    if(l<=lt&&rt<=r) return Tr[cur];
    int mid=(lt+rt)>>1;
    return min(Query(cur<<1,lt,mid,l,r),Query(cur<<1|1,mid+1,rt,l,r)); 
}
int cnt0[maxn][60];
int root[maxn][60];
int TR[maxn*30],LS[maxn*30],RS[maxn*30],TOT;
void ADD(int lst,int &cur,int lt,int rt,int pos,int c){
    cur=++TOT;
    TR[cur]=TR[lst]+c;
    LS[cur]=LS[lst],RS[cur]=RS[lst];
    if(lt==rt) return ;
    int mid=(lt+rt)>>1;
    if(pos<=mid) ADD(LS[lst],LS[cur],lt,mid,pos,c);
    else ADD(RS[lst],RS[cur],mid+1,rt,pos,c);
}
int ASK(int cur,int lt,int rt,int l,int r){
    if(rt<l||r<lt) return 0;
    if(l<=lt&&rt<=r) return TR[cur];
    int mid=(lt+rt)>>1;
    return ASK(LS[cur],lt,mid,l,r)+ASK(RS[cur],mid+1,rt,l,r);
}
int lim[60];
void init(int n,const vector<long long> &a){
    for(int i=0;i<n;i++){
        int lh=0;
        for(int j=0;j<60;j++){
            if((1ll<<j)&a[i]) lh=j;
        }
        rk[i]=A[lh].size();
        A[lh].push_back(a[i]);
        pos[lh].insert(i);
    }
    for(int H=0;H<60;H++){
        if(A[H].size()==0) continue;
        if(A[H].size()==0) continue;
        for(int i=0;i<A[H].size();i++){
            A[H][i]-=(1ll<<H);
        }
        for(int i=0;i<A[H].size();i++){
            cnt0[i][H]=(A[H][i]==0);
            if(i>0) cnt0[i][H]+=cnt0[i-1][H];
        }        
        lim[H]=A[H].size()+14;
        build(1,1,lim[H]);
        Build(1,1,lim[H]);
        len=A[H].size()+1;
        int now=0;
        for(int rt=0;rt<A[H].size();rt++){
            if(A[H][rt]<=lim[H]&&A[H][rt]>0){
                pair<int,int> res=query(1,1,lim[H],A[H][rt],lim[H]);
                if(res.first==0){
                    //删除最大的在 [0,res.second] 中的操作
                    int id=Query(1,1,lim[H],1,res.second);
                    Del(1,1,lim[H],A[H][id],id);
                    ADD(now,now,1,lim[H],id+1,1);
                    add(1,1,lim[H],A[H][id],lim[H],1);
                }
                Ins(1,1,lim[H],A[H][rt],rt);
                add(1,1,lim[H],A[H][rt],lim[H],-1);
            }
            root[rt][H]=now;
        }
    }
}
long long ask(int l,int r){
    int L=l,R=r;
    L--,R--;
    int h=0;
    for(int i=0;i<60;i++){
        auto it=pos[i].lower_bound(L);
        if(it!=pos[i].end()){
            if((*it)<=R) h=i;
        }
    }
    auto it=pos[h].lower_bound(L);
    L=rk[(*it)];
    it=pos[h].upper_bound(R);
    it--;
    R=rk[(*it)];
    int ans=ASK(root[R][h],1,lim[h],L+1,lim[h]);
    ans+=cnt0[R][h];
    if(L>0) ans-=cnt0[L-1][h];
    return 2*(r-l+1)-((r-l+1)-(R-L+1))-ans+((1ll<<h));
}
vector<long long> askAll(int q,const vector<int> &l,const vector<int> &r){
    vector<long long> Res(q);
    for(int i=0;i<q;i++) Res[i]=ask(l[i],r[i]);
    return Res;
}