块状数组

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
const int N = 3e6 + 8;
int st[N], ed[N], siz[N], bel[N];
void init_block(int n)
{
    int sq = sqrt(n);
    for (int i = 1; i <= sq; ++i) {
        st[i] = n / sq * (i - 1) + 1;
        ed[i] = n / sq * i;
    }
    ed[sq] = n;
    for (int i = 1; i <= sq; ++i)
        for (int j = st[i]; j <= ed[i]; ++j)
            bel[j] = i;
    for (int i = 1; i <= sq; ++i)
        siz[i] = ed[i] - st[i] + 1;
}
int arr[N], mark[N];
vector<int> v[N]; // 这里用vector存排序后的数组
void update(int b) // 更新排序后的数组
{
    for (int i = 0; i <= siz[b]; ++i)
        v[b][i] = arr[st[b] + i];
    sort(v[b].begin(), v[b].end());
}
void eachT() {
    int n = read(), m = read();
    int sq = sqrt(n);
    init_block(n);
    for (int i = 1; i <= n; ++i)
        arr[i] = read();
    for (int i = 1; i <= sq; ++i)
        for (int j = st[i]; j <= ed[i]; ++j)
            v[i].push_back(arr[j]);
    for (int i = 1; i <= sq; ++i)
        sort(v[i].begin(), v[i].end());
    while (m--) {
        char o;
        scanf(" %c", &o);
        int l = read(), r = read(), k = read();
        if (o == 'M') {
            if (bel[l] == bel[r]) // 如果同属一块直接暴力
            {
                for (int i = l; i <= r; ++i)
                    arr[i] += k;
                update(bel[l]);
                continue;
            }
            for (int i = l; i <= ed[bel[l]]; ++i) // 对零散块暴力处理
                arr[i] += k;
            for (int i = st[bel[r]]; i <= r; ++i)
                arr[i] += k;
            update(bel[l]);
            update(bel[r]);
            for (int i = bel[l] + 1; i < bel[r]; ++i) // 打上标记
                mark[i] += k;
        } else {
            int tot = 0;
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; ++i)
                    if (arr[i] + mark[bel[l]] >= k)
                        tot++;
                printf("%d\n", tot);
                continue;
            }
            for (int i = l; i <= ed[bel[l]]; ++i)
                if (arr[i] + mark[bel[l]] >= k)
                    tot++;
            for (int i = st[bel[r]]; i <= r; ++i)
                if (arr[i] + mark[bel[r]] >= k)
                    tot++;
            // 二分查找k-mark[i]的位置，因为整块都加上了mark[i]其实就相当于k减去mark[i]
            for (int i = bel[l] + 1; i < bel[r]; ++i)
                tot += v[i].end() - lower_bound(v[i].begin(), v[i].end(), k - mark[i]);
            printf("%d\n", tot);
        }
    }
}

莫队

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
const int N = 3e6 + 8;
int sq;
struct query {
    int l, r, id;
    bool operator<(const query& o) const {
        // 这里只需要知道每个元素归属哪个块，而块的大小都是sqrt(n)，所以可以直接用l/sq
        if (l / sq != o.l / sq) return l < o.l;
        if (l / sq & 1) return r < o.r;
        return r > o.r;
    }  // 重载<运算符，奇偶化排序
} Q[N];
int arr[N], ans[N], Cnt[N], cur, l = 1, r = 0;
inline void add(int p) {
    if (Cnt[arr[p]] == 0)
        cur++;
    Cnt[arr[p]]++;
}
inline void del(int p) {
    Cnt[arr[p]]--;
    if (Cnt[arr[p]] == 0)
        cur--;
}
void eachT() {
    int n = read();
    sq = sqrt(n);
    for (int i = 1; i <= n; ++i) arr[i] = read();
    int q = read();
    for (int i = 0; i < q; ++i) Q[i].l = read(), Q[i].r = read(), Q[i].id = i; // 把询问离线下来
    sort(Q, Q + q); // 排序
    for (int i = 0; i < q; ++i) {
        while (l > Q[i].l) add(--l);
        while (r < Q[i].r) add(++r);
        while (l < Q[i].l) del(l++);
        while (r > Q[i].r) del(r--);
        ans[Q[i].id] = cur; // 储存答案
    }
    for (int i = 0; i < q; ++i) printf("%d\n", ans[i]); // 按编号顺序输出
}