自动搬运

查看原文

来自洛谷，原作者为

	RuntimeErr 在我遥远的褪去颜色的名字上，荣光之虹照耀我身

搬运于2025-08-24 21:52:06，当前版本为作者最后更新于2021-03-02 23:25:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的莫队+值域分块题解

保证简单易懂！

题意简化

令 $cnt_i$ 表示第 $i$ 种股票的持有人数，求 $cnt_i$的第 $k$ 小。

思路

考虑值域分块，注意值域是持有某种股票的人数（热度），所以范围是不超过 $n$ 的，我们令 $cnt1_i$ 表示第 $i$ 种股票的持有人数（热度）（用于整块查询），$cnt2_i$ 表示持有人数（热度）为 $i$ 的股票个数（用于块内查询），再开一个块数组 $tot$ 表示每个值域块的股票数量（跟 $cnt1$ 配合使用）。

考虑 $add$ 和 $del$ 函数，我们肯定是要先把当前股票原来的持有人数的贡献去掉，再加上新的贡献，这个很好理解吧。

//be是对应的块
//两个函数前半段都是去掉原来的贡献，后半段都是加上新的贡献
inline void add(int x){
    --cnt2[cnt1[x]];
    --tot[be[cnt1[x]]];
    ++cnt2[++cnt1[x]];//唯一的区别就是这一句了
    ++tot[be[cnt1[x]]];  
}
inline void del(int x){
    --cnt2[cnt1[x]];
    --tot[be[cnt1[x]]];
    ++cnt2[--cnt1[x]];
    ++tot[be[cnt1[x]]];
}

再来看查询部分，我们先按块查，把查询的 $k$ 每次都减去当前块的股票个数，若 $k$ 减去之后会小于等于 $0$ 那要找的块就是它了（若所有块都查完了 $k$ 还是大于 $0$ 那直接返回 $-1$），接着在块内按同样的方式，把 $k$ 每次都减去该热度的持股数量，直到 $k$ 小于等于 $0$ 就返回该热度。

inline int get(int k){
    int i;
    for(i=1;i<=num;++i){//num是块数
        if(k-tot[i]<=0)break;//找到了就退出
        k-=tot[i];
    }
    if(i==num+1)return -1;//所有块都查完了还没找到就返回-1
    for(int j=L[i];j<=R[i];++j){
        if(k-cnt2[j]<=0)return j;//找到了就返回
        k-=cnt2[j];
    }
}

！！！值域甚大，须离散化

$Code:$

#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N=1e5+10;

int n,m,a[N],b[N],ans[N];
int bl,L[N],R[N],be[N],num,tot[N],cnt1[N],cnt2[N];
struct query{int l,r,k,id;}q[N];

inline bool cmp(query a,query b){
    return be[a.l]^be[b.l]?a.l<b.l:be[a.l]&1?a.r<b.r:a.r>b.r;
}

inline void add(int x){
    --cnt2[cnt1[x]];
    --tot[be[cnt1[x]]];
    ++cnt2[++cnt1[x]];
    ++tot[be[cnt1[x]]];  
}
inline void del(int x){
    --cnt2[cnt1[x]];
    --tot[be[cnt1[x]]];
    ++cnt2[--cnt1[x]];
    ++tot[be[cnt1[x]]];
}
inline int get(int k){
    int i;
    for(i=1;i<=num;++i){
        if(k-tot[i]<=0)break;
        k-=tot[i];
    }
    if(i==num+1)return -1;
    for(int j=L[i];j<=R[i];++j){
        if(k-cnt2[j]<=0)return j;
        k-=cnt2[j];
    }
}

int main(){
    scanf("%d%d",&n,&m);bl=pow(n,0.455);
    
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    
    for(int i=1,tmp=-1;i<=n;++i){
        be[i]=(i-1)/bl+1;
        if(tmp^be[i])L[++num]=i,tmp=be[i];
        R[num]=i;
    }
    
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].id=i;
    }
    sort(q+1,q+m+1,cmp);
    
    for(int i=1,l=q[1].l,r=l-1;i<=m;++i){
        while(l>q[i].l)add(a[--l]);
        while(r<q[i].r)add(a[++r]);
        while(l<q[i].l)del(a[l++]);
        while(r>q[i].r)del(a[r--]);
        ans[q[i].id]=get(q[i].k);
    }
    for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
    return 0;
}