P3730 莫队+值域分块题解

· · 题解

莫队+值域分块题解

题意简述

查询区间内出现次数第k小的值的出现次数。

1\leq N, M\leq 10^5

题目分析

这种 1e5 又不带修改的规模容易想到莫队。但是使用平衡树之类 O(\log n) 插入 O(\log n) 查询的数据结构搭配莫队，会使复杂度变成 O(n \sqrt n \log n)，无法通过此题。

考虑平衡复杂度，莫队有 n \sqrt n 次插入和 n 次查询操作，所以我们最理想的情况下就是找到一个 O(1) 插入 O(\sqrt n) 查询的数据结构。值域分块 可以解决这个问题，此时总复杂度为 O(n \sqrt n)。

一些细节

代码

#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100005,M = 320;
class inquiry{
    public:
        int l,r,x,block,id;
        inline bool operator < (const inquiry &tmp)const{
            if(block!=tmp.block)//奇偶性优化，个人感觉不是对时间优化，而是防出题人卡莫队
                return l<tmp.l;
            return block&1?r<tmp.r:r>tmp.r;
        }
};
vector<inquiry> qus;
int ans[N],cnt[N];
vector<int> has;
int block,len;
int a[N];
int n,m;

namespace sqrtrange{//值域分块
    int cnt[N],sum[M];

    inline void update(int x,int c){
        cnt[x] += c;
        sum[x/len] += c;//更新所在块的贡献
    }

    inline int query(int x){
        int top = ceil(n*1.0/len);
        for(int k=0;k<top;k++){
            if(x>sum[k])//答案不在块内
                x -= sum[k];
            else{//答案在块内，遍历整个块寻找答案
                int l = k*len,r = min((k+1)*len,n);
                for(int j=l;j<=r;j++){
                    if(x>cnt[j])
                        x -= cnt[j];
                    else
                        return j;
                }
            }
        }
        return -1;
    }
}

inline int h(int x){
    return lower_bound(has.begin(),has.end(),x)-has.begin();
}

inline void add(int x){
    if(cnt[a[x]])
        sqrtrange::update(cnt[a[x]],-1);//减去修改前出现次数的贡献
    cnt[a[x]]++;
    sqrtrange::update(cnt[a[x]],1);//更新贡献
}

inline void del(int x){
    sqrtrange::update(cnt[a[x]],-1);
    cnt[a[x]]--;
    if(cnt[a[x]])
        sqrtrange::update(cnt[a[x]],1);
}

int main(){
    n = in(),m = in();
    block = ceil(n/sqrt(m));
    for(int k=1;k<=n;k++)
        has.emplace_back(a[k]=in());
    sort(has.begin(),has.end());
    has.erase(unique(has.begin(),has.end()),has.end());
    for(int k=1;k<=n;k++)
        a[k] = h(a[k]);
    len = ceil(sqrt(n));
    for(int k=1;k<=m;k++){
        int l = in(),r = in(),x = in();
        qus.push_back({l,r,x,l/block,k});
    }
    sort(qus.begin(),qus.end());
    int L = 1,R = 0;
    for(auto[l,r,x,tmp,id]:qus){
        while(l<L)
            add(--L);
        while(l>L)
            del(L++);
        while(r<R)
            del(R--);
        while(r>R)
            add(++R);
        ans[id] = sqrtrange::query(x);
    }
    for(int k=1;k<=m;k++){
        out(ans[k]);
        putchar('\n');
    }
    return 0;
}

后话