だから僕らは がんばって挑戦だよね

P3730 莫队+值域分块题解

  • ~3.31K 字
  1. 1. 莫队+值域分块题解
    1. 1.1. 题意简述
    2. 1.2. 题目分析
      1. 1.2.1. 一些细节
    3. 1.3. 代码
      1. 1.3.1. 后话

“生きる熱さを感じたいだけさ”—— 《スリリング・ワンウェイ》

莫队+值域分块题解

题意简述

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

1≤N,M≤1051\leq N, M\leq 10^5

题目分析

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

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

一些细节

  • 题目值域是 [1,109][1,10^9]，需要离散化。
  • 莫队的最优块长其实是 nm\dfrac{n}{\sqrt m}。因为 nn 和 mm 同价的时候和 n\sqrt n 是一样的，一般也没理这个事。证明详见 普通莫队算法 - Oi Wiki。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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;
}

后话

  • 这种莫队套分块去平衡复杂度还挺常见的，有时候也搭配 bitset。
  • 第一次写题解，水平有限还请见谅。
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可