Theo dữ kiện đề bài thì xét đến vị trí $x_i$ thì chúng ta mới bắt đầu mua $a_i$ cây táo trong đoạn $[l_i,r_i]$ . Vậy thay vì đến vị trí $x_i$ mới mua thì bây giờ chúng ta bắt đầu mua từ vị trí $1$ và $a_i$ bây giờ được cộng thêm $1$ lượng $k$ với $k$ là số lượng số thoả mãn $l_i \le A_j \le r_i$ với $j = [1,x_i)$. Đến bước này, chúng ta chỉ cần tìm kiếm nhị phân song song và gần giống với bài Cây táo $2$ thoi. Đây là code mẫu của mình:

/*    /\_/\
     ( ._. )  ~UwU~
     / >0< \
/*Author fxt*/
#include<bits/stdc++.h>
using namespace std;
#define fast            ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int             long long
#define el              '\n'
#define pb              push_back
#define FOU(i, a, b)    for(int i=(a), _b = (b); i<=_b; ++i)
#define FOD(i, a, b)    for(int i=(a), _b = (b); i>=_b; --i)
#define REP(i, n)       for(int i= 0, _n = (n); i<_n ;++i)
const int N = 2e5+7;
struct node
{
    int l,r,x;
};
int n,k,m,q,bit[N],a[N],cnt[N],res[N];
node Q[N];
vector<int> run;
vector<node> lastx[N];
void up(int x,int v=1){
    for (;x<N;x+=x&-x) bit[x]+=v;
}
int get(int x){
    int s = 0;
    for (;x>0;x-=x&-x) s+=bit[x];
    return s;
}
int query(int l,int r){
    return get(r)-get(l-1);
}
void calc(int l,int r,vector<int> & rec){
    if (l>r || rec.empty()) return;
    int mid = (l+r)>>1;
    FOU(i,l,mid) up(a[i]);
    vector<int> ok,notok;
    for (int id:rec){
        int s = query(Q[id].l,Q[id].r);
        if (s>=cnt[id]){
            ok.pb(id);
            res[id] = mid;
        }else{
            notok.pb(id);
            cnt[id]-=s;
        }
    }
    FOU(i,l,mid) up(a[i],-1);
    calc(l,mid-1,ok);
    calc(mid+1,r,notok);
    vector<int>().swap(ok);
    vector<int>().swap(notok);
}
void solve(){
    cin >> n >> q;
    FOU(i,1,n) cin >> a[i];
    FOU(i,1,q){
        cin >> Q[i].l >> Q[i].r >> Q[i].x >> cnt[i];
        run.pb(i);
        lastx[Q[i].x-1].pb({Q[i].l,Q[i].r,i});
        res[i] = -1;
    }
    FOU(i,1,n){
        up(a[i]);
        for (node T:lastx[i]){
            cnt[T.x] +=query(T.l,T.r);
        }
    }
    FOU(i,1,n) up(a[i],-1);
    calc(1,n,run);
    FOU(i,1,q) cout << res[i] << ' ';
}
signed main(){
    fast
    solve();
    return 0;
}