Dyd's Blog

He who has a strong enough why can bear almost any how.

分块和块状链表

Posted on Edited on In
Symbols count in article: 5.8k Reading time ≈ 5 mins.

暴力真的出了奇迹

基本思想

对于一个长为 $n$ 的序列，把它分为 $\sqrt{n}$ 个“块”，“块”内的操作暴力求解，跨“块”的操作用“块”中的信息计算。

例题

由于分块是一种思想，我们用一道例题具体分析。
AcWing243一个简单的整数问题2
本题标程是线段树求解，用分块虽然效率不如，但思路和代码难度较之间单不少。

分析

  1. 把序列分为 $\sqrt{n}$ 个“块”

  2. 对于操作一，区间 $[l,r]$ 被分为若干个完整“块”和至多两个不完整“块”，不妨在完整“块”上打一个懒标记，定义 $add$ 为“本‘块’中的所有数都要加上 $add$ ”，而不完整块暴力解决

  3. 对于操作二，区间 $[l,r]$ 被分为若干个完整“块”和至多两个不完整“块”，同上可定义 $sum$ 为“本‘块’中所有数的真实的，即算了 $add$ 的和”，而不完整块暴力解决

总的来说，就是“整‘块’懒标记，‘块’内打暴力”。修改和查询的时间复杂度都为 $O(\sqrt{n})$ ，大于线段树的 $O(\log n)$ （当 $n=10^5$ 时， $\sqrt{n} \approx 317$ 而 $\log n \approx 17$ ），但分块的思路和代码难度都简单不少。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5, M = 350;
int n, m, len;
int w[N];
struct Block
{
    LL add, sum;
#define add(i) b[i].add
#define sum(i) b[i].sum
} b[M];
//判断x对应第几块
int get(int x) 
{
    return (x - 1) / len; //减一可以保证第0块一定有len个
}
void change(int l, int r, int d) 
{
    if (get(l) == get(r))
        for (int i = l; i <= r; ++i)
            w[i] += d, sum(get(i)) += d;
    else 
	{
        int i = l, j = r;
        while (get(i) == get(l))
            w[i] += d, sum(get(i)) += d, ++i;
        while (get(j) == get(r))
            w[j] += d, sum(get(j)) += d, --j;
        for (int k = get(i); k <= get(j); ++k)
            sum(k) += len * d, add(k) += d;
    }
}
LL query(int l, int r) 
{
    LL res = 0;
    if (get(l) == get(r))
        for (int i = l; i <= r; ++i)
            res += w[i] + add(get(i));
    else 
	{
        int i = l, j = r;
        while (get(i) == get(l))
            res += w[i] + add(get(i)), ++i;
        while (get(j) == get(r))
            res += w[j] + add(get(j)), --j;
        for (int k = get(i); k <= get(j); ++k)
            res += sum(k);
    }
    return res;
}
int main() {
    scanf("%d%d", &n, &m);
    len = sqrt(n);
    for (int i = 1; i <= n; ++i) 
	{
        scanf("%d", &w[i]);
        sum(get(i)) += w[i];
    }
    char op[2];1. 
    int l, r, d;
    while (m--)
	 {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'C') 
		{
            scanf("%d", &d);
            change(l, r, d);
        } 
		else
            printf("%lld\n", query(l, r));
    }
    return 0;
}

块状链表

我们已经用分块的思想实现了修改和查询操作，但是，如何实现插入、删除操作呢？
我们发现，对于一个序列，插入新数后，其分块方式就变了，必须更新每一块！每一块都要重新计算，太过麻烦，且时间复杂度过大。
为此，我们只好换一种分块方式——用链表的形式储存块，相邻两块之间用指针相连。
块状链表

插入/删除

进行插入操作（如在块 $[l,r]$ 中插入一段 $[a,b]$ ）时，我们如下操作：

  1. 把 $[l,r]$ 断开，并把断开后的两段用指针相连
    分段

  2. 把 $[a,b]$ 构建成一个块状链表
    构造

  3. 把断开的两段间的指针指向 $[a,b]$
    插入

同理，删除操作：

  1. 删除开头块中被区间覆盖的部分，具体方法为：把本块被覆盖前的点后移，覆盖掉需要被删除的点，并更新长度
    删除前

  2. 删除中间的完整块，具体方法为：调整两端指针，回收中间指针
    删除中

  3. 删除结尾块被覆盖的部分，具体方法为：把本块被覆盖的点后的点前移，覆盖掉需要被删除的点，并更新长度删除后

但是聪明的人已经发现了，这样做的一个问题——无法保证每个块的长度均匀，甚至会有块中只有1、2个数，这样会导致块非常多，严重影响我们的效率。

合并

为了解决那些长度很小的块，我们需要定期合并一些块。合并方法如下：

  1. 遍历每个块

  2. 对于每个块，若下一个块可以合并在当前块中（即当前块的长度加下一个块的长度小于等于最大长度，即 $\sqrt{n}$ ），就进行合并。具体方法为： 将下一个块复制到当前块，删除下一个块。

进行完如下操作后，剩下的块中任意相邻两块的长度和是一定大于 $\sqrt{n}$ 的，这样平均下来每一段的长度大于 $\frac{\sqrt{n}}{2}$ 总的段数小于 $2\sqrt{n}$ 。

例题

P4008
代码： 

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5, M = 2000 + 5;
int n, x, y; //n:操作个数,x、y:光标位置
struct Bolck
{
    char s[N + 1];
    int c;    //字符个数
    int l, r; //左右指针
} p[M];
char str[20000000 + 5];
int q[M], tt; //内存缓冲区
//光标移动到第k个字符后
void move(int k)
{
    x = p[0].r;
    while (k > p[x].c)
        k -= p[x].c, x = p[x].r;
    y = k - 1;
}
//将节点v插入到节点u右边
void add(int u, int v)
{
    p[v].r = p[u].r, p[p[u].r].l = v;
    p[u].r = v, p[v].l = u;
}
//删除节点u
void del(int u)
{
    p[p[u].l].r = p[u].r;
    p[p[u].r].l = p[u].l;
    p[u].l = p[u].r = p[u].c = 0;
    q[++tt] = u; //回收节点u
}
//在光标后插入k个字符
void insert(int k)
{
    //若是在节点内插入,必须先将节点分裂成在节点末尾插入
    if (y < p[x].c - 1)
    {                                        //从光标处分裂
        int u = q[tt--];                     //新建节点
        for (int i = y + 1; i < p[x].c; ++i) //复制后段到新建节点
            p[u].s[p[u].c++] = p[x].s[i];
        p[x].c = y + 1;
        add(x, u);
    }

    int cur = x;
    for (int i = 0; i < k;)
    {
        int u = q[tt--];            //新建节点
        while (p[u].c < N && i < k) //在当前节点装满前一直装
            p[u].s[p[u].c++] = str[i++];
        add(cur, u);
        cur = u;
    }
}
//删除光标后的k个字符
void remove(int k)
{
    //若是在节点内删除,只需前后覆盖即可
    if (p[x].c - 1 - y >= k)
    {
        for (int i = y + k + 1, j = y + 1; i < p[x].c; ++i, ++j)
            p[x].s[j] = p[x].s[i];
        p[x].c -= k;
    }
    //否则必须分类
    else
    {
        //除去前面节点内部的部分
        k -= p[x].c - y - 1;
        p[x].c = y + 1;
        //把中间整段删除
        while (p[x].r && k >= p[p[x].r].c)
        {
            int u = p[x].r;
            k -= p[u].c;
            del(u);
        }
        //删除后面节点内部的部分
        int u = p[x].r;
        for (int i = 0, j = k; j < p[u].c; ++i, ++j)
            p[u].s[i] = p[u].s[j];
        p[u].c -= k;
    }
}
//输出光标后的k个字符(类似删除)
void get(int k)
{
    if (p[x].c - 1 - y >= k)
        for (int i = 0, j = y + 1; i < k; ++i, ++j)
            putchar(p[x].s[j]);
    else
    {
        k -= p[x].c - y - 1;
        for (int i = y + 1; i < p[x].c; ++i)
            putchar(p[x].s[i]);

        int cur = x;
        while (p[cur].r && k >= p[p[cur].r].c)
        {
            int u = p[cur].r;
            for (int i = 0; i < p[u].c; ++i)
                putchar(p[u].s[i]);
            k -= p[u].c;
            cur = u;
        }

        int u = p[cur].r;
        for (int i = 0; i < k; ++i)
            putchar(p[u].s[i]);
    }
    puts("");
}
//光标前移
void front()
{
    if (!y)
    {
        x = p[x].l;
        y = p[x].c - 1;
    }
    else
        y--;
}
//光标后移
void after()
{
    if (y < p[x].c - 1)
        y++;
    else
    {
        x = p[x].r;
        y = 0;
    }
}
//将相邻节点合并
void merge()
{
    for (int i = p[0].r; i; i = p[i].r)
        while (p[i].r && p[i].c + p[p[i].r].c < N)
        {
            int r = p[i].r;
            for (int j = p[i].c, k = 0; k < p[r].c; ++j, ++k)
                p[i].s[j] = p[r].s[k];

            if (x == r)
                x = i, y += p[i].c; //更新光标位置

            p[i].c += p[r].c;
            del(r);
        }
}
int main()
{
    for (int i = 1; i < M; ++i)
        q[++tt] = i;
    scanf("%d", &n);
    char op[10];
    //插入哨兵,把光标移动到开头
    str[0] = '>';
    insert(1);
    move(1);

    while (n--)
    {
        int a;
        scanf("%s", op);
        if (!strcmp(op, "Move"))
        {
            scanf("%d", &a);
            move(a + 1); //因为有一个哨兵
        }
        else if (!strcmp(op, "Insert"))
        {
            scanf("%d", &a);
            int i = 0, k = a;
            while (a)
            {
                str[i] = getchar();
                if (str[i] >= 32 && str[i] <= 126)
                    i++, a--;
            }
            insert(k);
            merge();
        }
        else if (!strcmp(op, "Delete"))
        {
            scanf("%d", &a);
            remove(a);
            merge();
        }
        else if (!strcmp(op, "Get"))
        {
            scanf("%d", &a);
            get(a);
        }
        else if (!strcmp(op, "Prev"))
            front();
        else
            after();
    }
    return 0;
}