题目概述

下克上の天邪鬼

解题报告

顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lfloor{a_i\over 2}\rfloor$ 来优化复杂度。

先找出 $[l_1,r_1]$ 内 $a_i$ 最大值 $A$ ，然后查询 $[l_2,r_2]$ 中 $[{\lfloor{A\over 2}\rfloor},A-1]$ 的 $a_j$ 最大值，如果 $a_j$ 不存在，那么我们就必须从 ${\lfloor{A\over 2}\rfloor}-1$ 往前考虑了。否则如果找到了，答案就是 $A+a_j$ 。

将条件反过来写，则 $a_j<a_i\le 2a_j+1$ ，因此我们找到 $[l_2,r_2]$ 中 $[1,{\lfloor{A\over 2}\rfloor}-1]$ 范围内 $a_j$ 最大值 $B$ ，然后反过来去找 $[l_1,r_1]$ 中 $[B+1,2B+1]$ 的 $a_i$ 最大值，如果还是没找到，我们就查询出 $[l_1,r_1]$ 中 $[1,B]$ 的 $a_i$ 最大值 $A$ ，然后重复上述步骤。否则如果找到了，答案就是 $B+a_i$ 。

上面的所有查询操作都可以通过主席树上二分求出。

这样最多只会重复 $\log_210^9$ 次步骤，因此复杂度就是 $O(n\log_210^9+m\log_2^210^9)$ 。

示例程序

#include<cstdio>
using namespace std;
const int maxn=200000,maxt=1e7;

int n,m,a[maxn+5],ans;
int pl,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5],res;

inline int newnode() {pl++;return pl;}
int Insert(int p,int pos,int l=1,int r=1e9){
    int now=newnode();
    ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;
    if (l==r) return now;
    int mid=l+(r-l>>1);
    pos<=mid?ls[now]=Insert(ls[p],pos,l,mid):rs[now]=Insert(rs[p],pos,mid+1,r);
    return now;
}
void FindR(int A,int B,int L,int R,int l=1,int r=1e9){
    if (!(sum[B]-sum[A])) return;
    if (L==l && r==R){
        if (l==r) {res=l;return;}
        int mid=l+(r-l>>1);
        if (sum[rs[B]]-sum[rs[A]]) FindR(rs[A],rs[B],mid+1,R,mid+1,r);
        else FindR(ls[A],ls[B],L,mid,l,mid);
        return;
    }
    int mid=l+(r-l>>1);
    if (R<=mid) FindR(ls[A],ls[B],L,R,l,mid); else if (L>mid) FindR(rs[A],rs[B],L,R,mid+1,r); else {
        FindR(rs[A],rs[B],mid+1,R,mid+1,r);
        if (res) return;
        FindR(ls[A],ls[B],L,mid,l,mid);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),ro[i]=Insert(ro[i-1],a[i]);
    for (int i=1,A,B,C,D;i<=m;i++){
        scanf("%d%d%d%d",&A,&B,&C,&D);
        ans=0;
        res=0;FindR(ro[A-1],ro[B],1,1e9);
        for (int MAX=res;MAX>1;){
            int L=MAX/2,R=MAX-1;
            res=0;FindR(ro[C-1],ro[D],L,R);
            if (res) {ans=MAX+res;break;}
            if (L==1) break;
            res=0;FindR(ro[C-1],ro[D],1,L-1);
            if (!res) break;
            MAX=res;
            L=MAX+1;R=(MAX<<1)+1;
            res=0;FindR(ro[A-1],ro[B],L,R);
            if (res) {ans=MAX+res;break;}
            res=0;FindR(ro[A-1],ro[B],1,L-1);
            MAX=res;
        }
        printf("%d\n",ans);
    }
    return 0;
}