跳转至

莫队套数据结构

莫队套分块

P4396 [AHOI2013] 作业

题意

给定一个长度为 \(n\) 的序列 \(x\)；有 \(m\) 次询问，每次询问给定 \(l,r,a,b\)，询问序列区间 \([l,r]\) 中有多少个 \(i\) 满足 \(x_i\in [a,b]\)；以及有多少个不同的 \(x_i\in [a,b]\)。

\(n,m\le 10^5\)

本题有 \(poly(\log)\) 做法，请见 cdq 分治。

考虑莫队。维护一个桶数组，需要查询桶数组的区间和与区间不为 \(0\) 的数量。

然而莫队有 \(n\sqrt m\) 次修改，如果使用树状数组，时间复杂度将达到 \(O(n\sqrt m\log n)\)。

注意到查询操作总共产生的时间为 \(O(m\log n)\)，考虑平衡两者。若使用分块，则可以实现 \(O(1)\) 修改，\(O(\sqrt n)\) 查询，这样时间就降低为 \(O(n\sqrt m+m\sqrt n)\)。

这里树状数组比分块慢的原因是，莫队的修改操作和查询操作的数量不是平衡的。因此我们应该选用修改更快，查询更慢的非平衡数据结构。

代码 
 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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;

int blo[N], blen;
struct Query {
    int l, r, ql, qr, id;
    inline bool operator<(const Query& other) const {
        if(blo[l] != blo[other.l]) return blo[l] < blo[other.l];
        if(blo[l] & 1) return r > other.r;
        return r < other.r;
    }
} q[N];

struct block_array {
    int n, bl;
    int a[N], _sum[N];
    inline int blo(int x) { return (x + bl - 1) / bl; }
    inline void init(int _n, int _bl) {
        n = _n;
        bl = _bl;
        memset(a, 0, sizeof(a));
        memset(_sum, 0, sizeof(_sum));
    }
    inline int operator[](int index) const { return a[index]; }
    inline void set(int p, int v) {
        _sum[blo(p)] += v - a[p];
        a[p] = v;
    }
    inline void add(int p, int v) {
        set(p, a[p] + v);
    }
    inline int sum(int l, int r) {
        int res = 0;
        if(blo(l) == blo(r)) {
            for(int i = l; i <= r; i++) res += a[i];
            return res;
        }
        int x = blo(l) + 1, y = blo(r) - 1;
        while(blo(l) < x) res += a[l++];
        while(blo(r) > y) res += a[r--];
        for(int i = x; i <= y; i++) res += _sum[i];
        return res;
    }
};

int n, sn, m;
int a[N], ans1[N], ans2[N];

block_array cnt, vl;

int c_l, c_r;

void update(int pos, int w) {
    if(!cnt[a[pos]]) vl.set(a[pos], 1);
    cnt.add(a[pos], w);
    if(!cnt[a[pos]]) vl.set(a[pos], 0);
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r >> q[i].ql >> q[i].qr;
    for(int i = 1; i <= m; i++) q[i].id = i;

    blen = max(1, (int)(n / sqrt(m)));
    sn = max(1, (int)sqrt(n));
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;

    sort(q + 1, q + 1 + m);

    cnt.init(n, sn);
    vl.init(n, sn);

    c_l = 1, c_r = 0;
    for(int i = 1; i <= m; i++) {
        int l = q[i].l, r = q[i].r, ql = q[i].ql, qr = q[i].qr;
        while(c_r < r) update(++c_r, 1);
        while(c_l > l) update(--c_l, 1);
        while(c_r > r) update(c_r--, -1);
        while(c_l < l) update(c_l++, -1);
        ans1[q[i].id] = cnt.sum(ql, qr);
        ans2[q[i].id] = vl.sum(ql, qr);
    }

    for(int i = 1; i <= m; i++) {
        cout << ans1[i] << ' ' << ans2[i] << '\n';
    }

    return 0;
}