Hexo
0%

块状数组

Posted on In ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

块状数组

对整体数组进行分块执行

零散块暴力处理，适用于操作数较小时

对区间[l,r]的数加上k

询问[l,r]中有多少数大于c

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int maxn = 1e5 + 10;
const int SQ = 1e3 + 10;
/*
st[i]: 第i块的起始下标
ed[i]: 第i块的终止下标
size[i]: 第i块的长度
bel[i]: 下标为i的数据对应第几块
mark[i]: 第i块整块的修改值
*/
int n, m, a[maxn], st[SQ], ed[SQ], size[SQ], bel[maxn], mark[SQ];
vector<int> v[SQ]; // 第i块的集合

void init_block()
{
    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)
        size[i] = ed[i] - st[i] + 1;
}

void update(int t) // 更新排序后的数组
{
    for (int i = 0; i <= size[t]; ++i)
        v[t][i] = a[st[t] + i];
    sort(v[t].begin(), v[t].end());
}

void solve()
{
    cin >> n >> m;
    int sq = sqrt(n);
    init_block();
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    for (int i = 1; i <= sq; ++i)
    {
        for (int j = st[i]; j <= ed[i]; ++j)
            v[i].push_back(a[j]);
    }

    for (int i = 1; i <= sq; ++i)
        sort(v[i].begin(), v[i].end());

    while (m--)
    {
        int l, r, k, ope;
        cin >> ope >> l >> r >> k;
        if (ope == 1) // 将[l,r]的每个数加上k
        {
            if (bel[l] == bel[r]) // 同一块直接暴力
            {
                for (int i = l; i <= r; ++i)
                    a[i] += k;
                update(bel[l]);
                continue;
            }
            // 零散块处理
            for (int i = l; i <= ed[bel[l]]; ++i)
                a[i] += k;
            for (int i = st[bel[r]]; i <= r; ++i)
                a[i] += k;
            update(bel[l]);
            update(bel[r]);
            for (int i = bel[l] + 1; i < bel[r]; ++i) // 中间一大段的块直接打标记
                mark[i] += k;
        }
        else//查找[l,r]中大于等于k的个数
        {
            int sum = 0;
            if(bel[l]==bel[r])
            {
                for (int i = l; i <= r;++i)
                {
                    if(a[i]+mark[bel[i]]>=k)
                        sum++;
                }
                cout << sum << endl;
                continue;
            }
            for (int i = l; i <= ed[bel[l]];++i)
            {
                if(a[i]+mark[bel[i]]>=k)
                    sum++;
            }
            for (int i = st[bel[r]]; i <= r;++i)
            {
                if(a[i]+mark[bel[i]]>=k)
                    sum++;
            }
            //二分查找k-mark[i]的位置
            for (int i = bel[l] + 1; i < bel[r] - 1;++i)
            {
                sum += v[i].end() - lower_bound(v[i].begin(), v[i].end(), k - mark[i]);
            }
            cout << sum << endl;
        }
    }
}

int main()
{
    // std::ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        solve();
    }
    return 0;
}