题解 P3730 曼哈顿交易

· · 题解

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

保证简单易懂！

题意简化

令 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;
}