mydcwfy's Blog

Sqrt algorithm

Posted on
Symbols count in article: 5.7k Reading time ≈ 12 mins.

优雅的暴力，注意可以在线。

分块

1. 主要思想

分块其实是一个很好的 “暴力”，在 oi 赛制中性价比很高。

很好写，且实际得分也不低。

首先，分块本身就是一种思想。

我们可以回忆一下这道题：

T1：线段树1/你能回答这些问题吗2

题目传送门 Luogu

题目传送门 AcWing

前面，我们使用了树状数组和线段树维护了本题。

现在，我们使用分块。

分块就是将整个序列分为若干个段（一般为 $\sqrt{n}$），然后每一段维护整段信息。

比如，我们现在要从 l 到 r 每个数加 d。

一类是整段直接加，另一类是朴素加。

整段的个数 $\leq \sqrt{n}$，首尾朴素个数 $\leq \sqrt{n}$。

询问也类似。

然后，怎样区间直接加呢？

其实，我们可以类比于线段树的 lazytag，对于整段维护一个 add，代表整段加了多少。

同时，我们要询问整段的总和，所以要维护 sum。

注意，一定要弄清 sum 与 add 的关系。

我的思想与代码，都是 sum 已经加过了 add，你也可以设为没有加过。

下面，我们以此题为例，具体分析怎样操作。

2. 操作

1）修改

首先，维护整段。

然后，朴素两边。

单次复杂度为 $O(\sqrt{n})$

2）查询

首先，直接加整段。

然后，朴素加。

3. 例题

T1：线段树1/你能回答这些问题吗2

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define get(i) (i/len)
#define ll long long
using namespace std;

const int N=1e5+10,M=400;

int n,m,len;
ll add[M],sum[M],a[N];

void change(int l,int r,int x)
{
    if (get(l)==get(r))
    {
        for (int i=l;i<=r;++i) a[i]+=x,sum[get(i)]+=x;
    }
    else{
        int i=l,j=r;
        while (get(i)==get(l)) sum[get(i)]+=x,a[i]+=x,i++;
        while (get(j)==get(r)) sum[get(j)]+=x,a[j]+=x,j--;
        for (int k=get(i);k<=get(j);++k) sum[k]+=len*x,add[k]+=x;
    }
}

ll query(int l,int r)
{
    ll ans=0;
    if (get(l)==get(r))
    {
        for (int i=l;i<=r;++i) ans+=a[i]+add[get(i)];
    }
    else{
        int i=l,j=r;
        while (get(i)==get(l)) ans+=a[i]+add[get(i)],i++;
        while (get(j)==get(r)) ans+=a[j]+add[get(j)],j--;
        for (int k=get(i);k<=get(j);++k) ans+=sum[k];
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    len=sqrt(n);
    for (int i=1;i<=n;++i)
    {
        scanf("%lld",a+i);
        sum[get(i)]+=a[i];
    }
    int l,r,x;
    char op[5];
    while (m--)
    {
        scanf("%s %d %d",op,&l,&r);
        if (op[0]=='Q')
        {
            printf("%lld\n",query(l,r));
        }
        else{
            scanf("%d",&x);
            change(l,r,x);
        }
    }
    return 0;
}

AcWing,Luogu 实测数据。

算法 Luogu 时间 AcWing 时间 理论复杂度 空间
树状数组 131 ms 144 ms $O(n\log n)$ 5.71MB
线段树 246 ms 364 ms $O(n\log n)$ 7.49MB
分块 391 ms 891 ms $O(n\sqrt n)$ 1.34MB

块状链表

1. 主要思想

在上一题，我们使用了数组进行分块。

但是，如果是需要插入的话，我们就不得不换用另外的数据结构——链表。

加上分块，就有了一个高大上的名字：“块状链表”。

每两个块间，都有一个双向指针。

但是，又有不同的是，由于要支持插入，每一段的长度不是固定的。

2. 支持操作

a. 插入

首先，我们将要插入的节点所在块分裂开来，然后将插入的序列改为块状链表，插入即可。

b. 删除

首先将前面节点的后面部分删除，然后删除中间完整节点，最后删除后面节点的前面部分。

删除前面部分时，我们可以将剩下元素直接复制到前面，更新长度即可。

c. 合并

由于不停地分裂，可能导致节点很多而每一段很少，所以需要定期合并。

直接遍历整个块状链表，若下一个节点可以合并到当前节点，就合并。

合并结束后，每一个节点长度 $\geq \dfrac{\sqrt{n}}{2}$，总节点 $\leq 2\sqrt{n}$。

说实话，这可算是十分毒瘤的数据结构了。

主要是比较少写，而且没有固定的写法。

加油吧！

3. 例题

T2：[NOI2004]文本编辑器

题目传送门 Luogu

题目传送门 AcWing

可以用 Splay,也可以使用块状链表。

调了 2 个多小时后，AC 代码出炉了！

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

const int N=2005,M=2005;

struct Node{
    char s[N+1];
    int c,l,r;
}p[M];

char str[2000005];
int q[M],tt,x,y;

void del(int k)
{
    p[p[k].l].r=p[k].r;
    p[p[k].r].l=p[k].l;
    p[k].l=p[k].r=p[k].c=0;
    q[++tt]=k;
}

void add(int x,int k)
{
    p[k].r=p[x].r,p[p[x].r].l=k;
    p[k].l=x,p[x].r=k;
}

void prev()
{
    if (!y)
    {
        x=p[x].l;
        y=p[x].c-1;
    }
    else y--;
}

void next()
{
    if (y!=p[x].c-1) y++;
    else
    {
        x=p[x].r;
        y=0;
    }
}

void move(int k)
{
    int u=p[0].r;
    while (k>p[u].c) k-=p[u].c,u=p[u].r;
    x=u,y=k-1;
}

void insert(int k)
{
    if (y!=p[x].c-1)
    {
        int u=q[tt--];
        add(x,u);
        for (int j=y+1;j<p[x].c;++j) p[u].s[p[u].c++]=p[x].s[j];
        p[x].c=y+1;
    }
    int cur=x;
    for (int i=0;i<k;)
    {
        int u=q[tt--];
        add(cur,u);
        while (p[u].c<N&&i<k) p[u].s[p[u].c++]=str[i++];
        cur=u;
    }
}

void merge()
{
    for (int k=p[0].r;k;k=p[k].r)
        while (p[k].r&&p[k].c+p[p[k].r].c<N)
        {
            for (int j=p[k].c,i=0;i<p[p[k].r].c;++i,++j) p[k].s[j]=p[p[k].r].s[i];
            if (x==p[k].r) x=k,y+=p[k].c;
            p[k].c+=p[p[k].r].c;
            del(p[k].r);
        }
}

void remove(int k)
{
    if (p[x].c-y-1>=k)
    {
        for (int i=y+1,j=y+k+1;j<p[x].c;++i,++j) p[x].s[i]=p[x].s[j];
        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 cur=p[x].r;
            k-=p[cur].c;
            del(cur);
        }
        int cur=p[x].r;
        for (int i=0,j=k;j<p[cur].c;++i,++j) p[cur].s[i]=p[cur].s[j];
        p[cur].c-=k;
    }
}

void get(int k)
{
    if (p[x].c-y-1>=k)
    {
        for (int i=0;i<k;++i) putchar(p[x].s[y+i+1]);
        puts("");
    }
    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 r=p[cur].r;
            for (int i=0;i<p[r].c;++i) putchar(p[r].s[i]);
            k-=p[r].c;
            cur=r;
        }
        cur=p[cur].r;
        for (int i=0;i<k;++i) putchar(p[cur].s[i]);
        puts("");
    }
}

int main()
{
    // freopen("AcWing947_1.in","r",stdin);
    // freopen("myans.out","w",stdout);
    for (int i=1;i<M;++i) q[++tt]=i;
    int n,l;scanf("%d",&n);
    char op[10],c;
    str[0]='>';
    insert(1);
    move(1);
    while (n--)
    {
        scanf("%s",op);
        if (strcmp(op,"Insert")==0)
        {
            scanf("%d",&l);
            int i=0;
            while (i<l)
                if ((c=getchar())>=32&&c<=126) str[i++]=c;
            insert(l);
            merge();
        }
        else if (strcmp(op,"Move")==0)
        {
            scanf("%d",&l);
            move(l+1);
        }
        else if (strcmp(op,"Delete")==0)
        {
            scanf("%d",&l);
            remove(l);
            merge();
        }
        else if (strcmp(op,"Get")==0)
        {
            scanf("%d",&l);
            get(l);
        }
        else if (strcmp(op,"Prev")==0) prev();
        else if (strcmp(op,"Next")==0) next();
    }
    return 0;
}