CF840D 题解

123456wjc · 2026-10-22 13:23:53 · 题解

题意解析

区间查询最小的数字，使得该数字出现次数严格大于 t=\frac{r-l+1}{k}，其中 k 非常小。

做法介绍

首先有一个关键的洞察，就是给整个区间排序后相同元素连续段必有一段长度超过阈值，而阈值 t 又非常大。因此，在排序数组上每隔 t 个位置进行一个采样，采样结果必然包含答案（若答案存在）。因此，问题转换为求区间 k 小值和区间查询数字出现次数。

主席树当然可以做，但是常数稍大。针对这种二维数点问题，另一种比较好的做法是小波矩阵。小波矩阵的思想就是逐位划分整个数组，常数非常小。

具体原理参见：小波矩阵模板题题解。

代码编写

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=3e5+10;
const int Inf=0x3f3f3f3f;
const int W=20;
struct Vect{
    ull msk[(N>>6)+3];
    int cnt[(N>>6)+3];
    int tot=0;
    int n;
    Vect(int l=N){
        n=l;
        memset(msk,0,sizeof(msk));
        memset(cnt,0,sizeof(cnt));
    }
    inline void set(int k,ull bit){
        msk[k>>6] |= bit << (k&63);
        tot+=bit;
    }
    inline void build(){
        for(int i=0;(i<<6)<n;i++){
            cnt[i+1]=cnt[i]+__builtin_popcountll(msk[i]);
        }
    }
    inline int query(int k){
        return cnt[k>>6] + __builtin_popcountll(msk[k>>6] & (1ull<<(k&63))-1);
    }
};
struct Wavelet_Matrix{
    Vect m[W];
    vector<int> tmp;
    int n;
    void init(int l,int *a){
        n=l;
        tmp.resize(n+3);
        int t=0;
        for(int j=0;j<W;j++) m[j].n=n;
        for(int i=1;i<=n;i++) tmp[i]=a[i];
        for(int j=W-1;j>=0;j--){
            t=0;
            for(int i=1;i<=n;i++) a[i]=tmp[i];
            for(int i=1;i<=n;i++) m[j].set(i,a[i]>>j&1);
            m[j].build();
            for(int i=1;i<=n;i++) if(a[i]>>j&1^1) tmp[++t]=a[i];
            for(int i=1;i<=n;i++) if(a[i]>>j&1) tmp[++t]=a[i];
        }
        return;
    }
    int query_kth(int l,int r,int k){
        for(int i=W-1;i>=0;i--){
            int tot=n-m[i].tot;
            int cl=m[i].query(l),cr=m[i].query(r+1);
            int cnt=(r-l+1)-(cr-cl);
            if(k>cnt){
                k-=cnt;
                l=tot+cl+1;
                r=tot+cr;
            }else{
                l-=cl;
                r-=cr;
            }
        }
        return tmp[l];
    }
    int query_cnt(int l,int r,int x){
        for(int i=W-1;i>=0 && l<=r;i--){
            int tot=n-m[i].tot;
            int cl=m[i].query(l),cr=m[i].query(r+1);
            if(x>>i&1){
                l=tot+cl+1;
                r=tot+cr;
            }else{
                l-=cl;
                r-=cr;
            }
        }
        return max(0,r-l+1);
    }
}matrix;
int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    matrix.init(n,a);
    for(int i=1;i<=q;i++){
        int l,r,k,ans=Inf;
        cin>>l>>r>>k;
        int t=(r-l+1)/k;
        for(int i=t+1;i<=(r-l+1);i+=(t+1)){
            int x=matrix.query_kth(l,r,i);
            if(matrix.query_cnt(l,r,x)>t) ans=min(ans,x);
        }
        cout<<(ans>n?-1:ans)<<'\n';
    }
}