这题的离线做法？

整体二分，TLE了

#include<iostream>
#include<cstdio>
#include<algorithm>
#define re register int
#define il inline
using namespace std;
const int N=5e4+10;
int n,m,a[N],b[N],tot,ans[N],c[N],sum[N][3];
struct Node{
    int l1,r1,l2,r2,id;
}q[N],q1[N],q2[N];
int tree[N<<2][3];
il void build(int k,int l,int r){
    if(l==r){
        tree[k][0]=c[l];
        tree[k][1]=sum[l][1];
        tree[k][2]=sum[l][2];
        return;
    }
    int mid=(l+r)>>1;
    build(k<<1,l,mid);
    build(k<<1|1,mid+1,r);
    tree[k][0]=tree[k<<1][0]+tree[k<<1|1][0];
    tree[k][1]=max(tree[k<<1][1],tree[k<<1|1][1]);
    tree[k][2]=max(tree[k<<1][2],tree[k<<1|1][2]);
}
il int Ask(int k,int l,int r,int L,int R,int op){
    if(l>=L&&r<=R)return tree[k][op];
    if(l>R||r<L){
        if(op==0)return 0;
        return -11451419;
    }
    int mid=(l+r)>>1;
    if(op==0){
        int res=0;
        if(L<=mid)res+=Ask(k<<1,l,mid,L,R,op);
        if(R>mid)res+=Ask(k<<1|1,mid+1,r,L,R,op);
        return res;
    }
    int res=-11451419;
    if(L<=mid)res=max(res,Ask(k<<1,l,mid,L,R,op));
    if(R>mid)res=max(res,Ask(k<<1|1,mid+1,r,L,R,op));
    return res;
}
il void solve(int l,int r,int L,int R){
    if(L>R)return;
    if(l>r){
        for(re i=L;i<=R;i++)
            ans[q[i].id]=b[r];
        return;
    }
    int mid=(l+r)>>1;
    for(re i=1;i<=n;i++){
        if(a[i]>=b[mid])c[i]=1;
        else c[i]=-1;
        sum[i][1]=sum[i-1][1]+c[i];
    }
    for(re i=n;i>=1;i--)sum[i][2]=sum[i+1][2]+c[i];
    build(1,1,n);
    int lt=0,rt=0;
    for(re i=L;i<=R;i++){
        int S=Ask(1,1,n,q[i].l1,q[i].r1,2)+Ask(1,1,n,q[i].r1+1,q[i].l2-1,0)+Ask(1,1,n,q[i].l2,q[i].r2,1)-sum[q[i].l2-1][1]-sum[q[i].r1+1][2];
//      cout<<S<<" "<<b[mid]<<" "<<q[i].id<<endl;
        if(S>=0){ //可以 
            rt++;
            q2[rt]=q[i];
        }
        else{
            lt++;
            q1[lt]=q[i];
        }
    }
    for(re i=1;i<=lt;i++)q[L+i-1]=q1[i];
    for(re i=lt+1;i<=lt+rt;i++)q[L+i-1]=q2[i-lt];
    solve(l,mid-1,L,L+lt-1);
    solve(mid+1,r,L+lt,R);
}
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    tot=1;
    for(re i=2;i<=n;i++){
        if(b[i]!=b[tot]){
            tot++;
            b[tot]=b[i];
        }
    }
    scanf("%d",&m);
    for(re i=1;i<=m;i++){
        scanf("%d%d%d%d",&q[i].l1,&q[i].r1,&q[i].l2,&q[i].r2);
        q[i].id=i;
    }
    solve(1,tot,1,m);
    for(re i=1;i<=m;i++)printf("%d\n",ans[i]);
    return 0;
}