CF840D

水题一道。n倍经验懒得写，放一道：P3567
完全参考的P3567的写法即可，在query当中修改一下查询部分即可。
左子树大小足够即为答案，若无答案则看右子树是否大小足够，若依然无答案则输出-1

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define e_b emplace_back
#define p_b push_back
#define fir first
#define sec second
#define IOS ios::sync_with_stdio(0),cin.tie(0)
using namespace std;
const int N=5e5+5,inf=1e9;
int n,q,a[N];
struct node{
    int sz,ls,rs;
}t[N*32];
int rt[N],tot;
void build(int p,int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    t[p].ls=++tot,build(tot,l,mid);
    t[p].rs=++tot,build(tot,mid+1,r);
}
void pp(int p){t[p].sz=t[t[p].ls].sz+t[t[p].rs].sz;}
void upd(int p,int l,int r,int k){
    if(l==r){t[p].sz++;return;}
    int mid=l+r>>1;
    if(k>mid){
        t[++tot]=t[t[p].rs],t[p].rs=tot;
        upd(tot,mid+1,r,k);
    }else{
        t[++tot]=t[t[p].ls],t[p].ls=tot;
        upd(tot,l,mid,k);
    }
    pp(p);
}
int query(int p1,int p2,int l,int r,int k){
    //if(!l||!r)return -1;
    if(l==r)return l;
    int lsz=t[t[p2].ls].sz-t[t[p1].ls].sz;
    int rsz=t[t[p2].rs].sz-t[t[p1].rs].sz;
    int mid=l+r>>1,res=-1;
    if(lsz>k){
        res=query(t[p1].ls,t[p2].ls,l,mid,k);
        if(res==-1&&rsz>k)res=query(t[p1].rs,t[p2].rs,mid+1,r,k);
    }
    else if(rsz>k)res=query(t[p1].rs,t[p2].rs,mid+1,r,k);
    return res;
}
signed main(){
    IOS;cin>>n>>q;
    rt[0]=++tot;
    build(rt[0],1,n);
    for(int i=1;i<=n;i++){
        cin>>a[i];rt[i]=++tot;
        t[rt[i]]=t[rt[i-1]];
        upd(rt[i],1,n,a[i]);
    }
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<query(rt[l-1],rt[r],1,n,(r-l+1)/k)<<'\n';
    }
}