分块算法

【思想】  分块思想的核心是将一个集合划分成若干个规模较小的子集。即让连续的序列组成一个块,便于进行处理。
为了便于处理,分块需要满足:
(1) 若子集规模很小, 对每个子集可使用关于子集规模的复杂度较高的算法。
(2) 若子集数目很少, 可以使用与整个集合规模有关的算法分别处理每个子集。
可以发现前两条性质其实是相互矛盾的, 因此为了均衡, 我们既不能让子集规模过大,
也不能让子集数目过大, 通常分块的大小都取n^0.5(根号n)。
通过预处理每一个分块,对于询问的区间,我们可以把其分为完全处于块中的区间与不完全处于块中的区间。完全处于块中的区间可以用预处理的结果得出答案,不完全处于块中的区间采用暴力枚举的方法。由于每个块的大小有限,所以枚举的时间复制度并不大。这样,算法的时间复杂度是O(n^0.5 * n)。
【优点】 分块算法的时间复杂度比一些数据结构的O(n logn)还大,那分块算法有什么用呢。但是,有些数据是普通的数据结构不能合并的,比如BZOJ2724: [Violet 6]蒲公英
题目大意是给定 n 个数, 每次询问区间[L, R]内的众数, 强制在线。
很明显,这题是用线段树不能解决的。分块算法则能很好的完成。
在此题中我们就预处理出两个量: cnt[i][j]表示i 这个元素在前 j 块中的出现次数,以及 ans[i][j] 表示第i 块到第 j 块这个区间的众数。这两个量都是能在 O(n^0.5)的时间内预处理出来的。 cnt[i][j]较为简单就不赘述; 求 ans[i][j] 时我们先枚举并固定 i , 当 i 确定后我们用一个数组来记录每个数字的出现次数, 初始时所有数字出现次数均为 0。 接着我们从第i 块左端点开始, 枚举之后的所有元素, 并更新出现次数的数组, 在这个程中我们是能求出当前众数的。 当枚举到的元素是某个块 j 的右端点时, 我们就知道 ans[i][j] 的值了, 不难发现这个做法复杂度是 O(n^0.5)的。

而对于询问,先找出完全被包含的分块,此时,答案要么是这些分块的众数,要么是不完全被包含的分块中的数。我们可以暴力将它们全部枚举一遍, 记录下它们当前的出现次数, 配合之前预处理的 cnt[i][ j], 我们可以快速的算出一个数在第 L 块到第 R 块间的出现次数, 加上它在那 O( n^0.5) 个单个元素中出现的次数, 就是它在询问区间内出现的总次数, 进而我们可以利用它来更新答案。

代码如下:


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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int N = 4 * 1e4 + 10, M = 2 * 1e2 + 5;

struct io  {
    io()  {
        freopen("dandelion.in", "r", stdin);
        freopen("dandelion.out", "w", stdout);
    }
    ~io()  {
        fclose(stdin);
        fclose(stdout);
    }
}z;

int Read()  {
    int val = 0, opt = 1;
    char ch;
    while (!(isdigit( ch = getchar() ) || ch == '-'));
    if (ch == '-') opt = -1;
    else val = ch - '0';
    while (isdigit(ch = getchar())) (val *= 10) += ch - '0';
    return val * opt;
}

int cnt[N][M], Ans[M][M], a[N], b[N], n, T, num, ti[N], End[M], s, L, p[N][M];

int wz(int i)  {
    return (i - 1) / s + 1;
}

void Find_cnt()  {
    for (int i = 1;i <= n; i++) p[a[i]][wz(i)]++;
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= L; j++)
            cnt[a[i]][j] = cnt[a[i]][j - 1] + p[a[i]][j];
}

int conut(int li, int ri, int Num)  {
    return cnt[Num][ri] - cnt[Num][li - 1];
}

void Find_Ans()  {
    int t1, t2;
    for (int i = 1;i <= L; i++)  {
        memset(ti, 0, sizeof ti);
        for (int j = End[i - 1] + 1;j <= n; j++)  {
            if (!Ans[i][wz(j)]) Ans[i][wz(j)] = Ans[i][wz(j) - 1];
            t1 = conut(i, wz(j), a[j]);
            t2 = conut(i, wz(j), Ans[i][wz(j)]);
            if ((t1 > t2) || (t1 == t2 && a[j] < Ans[i][wz(j)]))
                Ans[i][wz(j)] = a[j];
        }
    }
}

int Que(int last)  {
    long long l, r, lc, rc, ans, t1, t2;
    l = (Read() + last - 1) % n + 1, r = (Read() + last - 1) % n + 1;
    if (l > r) swap(l, r);
    lc = wz(l) + 1;
    rc = wz(r) - 1;
    ans = Ans[lc][rc];
    memset(ti, 0, sizeof ti);
    if (wz(l) == wz(r))  {
        ans = 0;
        for (int i = l;i <= r; i++)  {
            ti[a[i]]++;
            if (ti[a[i]] > ti[ans] || (ti[a[i]] == ti[ans] && ans > a[i])) ans = a[i];
        }
        return b[ans];
    }
    for (int i = l;i <= End[lc - 1]; ++i)  {
        ++ti[a[i]];
        t1 = ti[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1];
        t2 = ti[ans] + cnt[ans][rc] - cnt[ans][lc - 1];
        if (t1 > t2 || (t1 == t2 && ans > a[i])) ans = a[i];
    }
    for (int i = End[rc] + 1;i <= r; ++i)  {
        ++ti[a[i]];
        t1 = ti[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1];
        t2 = ti[ans] + cnt[ans][rc] - cnt[ans][lc - 1];
        if (t1 > t2 || (t1 == t2 && ans > a[i])) ans = a[i];
    }
    return b[ans];
}

int main(void)  {
   
    n = Read(), T = Read();
    for (int i = 1;i <= n; ++i)  a[i] = b[i] = Read();
    sort(b + 1, b + 1 + n);
    num = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1;i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + num, a[i]) - b;
    s = (int)sqrt(n), L = n / s;
    for (int i = 1;i <= L; ++i) End[i] = i * s;
    if (n % s) End[++L] = n;
    Find_cnt();
    Find_Ans();
    int mmp = 0;
    while (T--)
        printf("%d\n", mmp = Que(mmp));
   
    return 0;
}

这里附上另一题代码:BZOJ1878: [SDOI2009]HH的项链


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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>

using namespace std;

const int N = 5 * 1e4 + 10, M = 230;

struct io  {
    io()  {
        freopen("HH.in","r",stdin);
        freopen("HH.out","w",stdout);
    }
    ~io()  {
        fclose(stdin);
       fclose(stdout);
    }
}zdx;

int Read()  {
    int val = 0, opt = 1;
    char ch;
    while (!(isdigit( ch = getchar() ) || ch == '-'));
    if (ch == '-') opt = -1;
    else val = ch - '0';
    while (isdigit( ch = getchar() )) (val *= 10) += ch - '0';
    return val * opt;
}

int cnt[N][M], p[N][M], Ans[N][M], a[N], b[N], End[M], n, num, s, L, co[N];

int wz(int x)  {
    return (x - 1) / s + 1;
}

void Find_cnt()  {
    for (int i = 1;i <= n; i++)
        ++p[a[i]][wz(i)];
    for (int i = 1;i <= num; i++)
        for (int j = 1;j <= L; j++)
            cnt[i][j] = cnt[i][j - 1] + p[i][j];
}

void Find_Ans()  {
    for (int i = 1;i <= L; i++)  {
        memset(co, 0, sizeof co);
        for (int j = End[i - 1] + 1;j <= n; j++)  {
            if (!(j % s - 1)) Ans[i][wz(j)] = Ans[i][wz(j) - 1];
            if (!co[a[j]]) ++Ans[i][wz(j)];
            ++co[a[j]];
        }
    }
}

int work()  {
    int l = Read(), r = Read(), lc, rc, ans = 0;
    lc = wz(l) + 1;
    rc = wz(r) - 1;
    memset(co, 0, sizeof co);
    if (wz(l) == wz(r))  {
        for (int i = l;i <= r; i++)   {
            ans += !co[a[i]];
            ++co[a[i]];
        }
        return ans;
    }
    ans = Ans[lc][rc];
    for (int i = l;i <= End[lc - 1]; i++)  {
        ans += !(co[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1]);
        ++co[a[i]];
    }
    for (int i = End[rc] + 1;i <= r; i++)  {
        ans += !(co[a[i]] + cnt[a[i]][rc] - cnt[a[i]][lc - 1]);
        ++co[a[i]];
    }
    return ans;
}

int main(void)
{
    n = Read();
    for (int i = 1;i <= n; i++)  a[i] = b[i] = Read();
    sort(b + 1, b + 1 + n);
    num = unique(b + 1, b + 1 + n) - b -1;
    for (int i = 1;i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + num, a[i]) - b;
    s = (int)sqrt(n);
    L = n / s;
    for (int i = 1;i <= L; i++) End[i] = i * s;
    if (n % s) End[++L] = n;
    Find_cnt();
    Find_Ans();
    int T = Read();
    while (T--)
        printf("%d\n", work());

    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注