学习笔记 - 块状链表 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

学习笔记 - 块状链表

发表于 分类于 Valine：

原来就是个分块 :(

# 引入

有两大基本数据结构——链表和数组，在访问元素和修改元素这两个方面各有优劣：

  • 数组便于访问元素，即 $O(1)$ 查询；但是数组难以在中间插入/删除一个元素，需要 $O(n)$ 的复杂度进行移位；
  • 链表便于插入/删除元素，可以 $O(1)$ 实现；但是难以直接访问第 $i$ 个元素，需要 $O(n)$ 的复杂度遍历查找。

那么如果要两个方面兼备，就上Splay要均衡访问和插入的复杂度。这就用上了分块，进而形成了块状链表。

# 块状链表

块状链表的思想简单，即把原来的数组 $\sqrt n$（我觉得某些题目应该可以改变块的大小来达到最高效率）分块，每一块作为链表的一个元素用链表维护。

实际实现有两种，第一种是真的把数组作为链表的元素，第二种是把数组 $\sqrt n$ 分块后每一块都用小链表维护，然后 $\sqrt n$ 个小链表再用一个大链表串起来。

个人觉得第二种更灵活，以下以第二种写法为例。下图就是一个例子 $n=15,\lceil\sqrt n\rceil=4$：

png

实际实现过程中因为插入删除元素，可能导致一些块的大小小于 $\sqrt n$，在一些题目中需要调整（也有一些题目可以不管……），后面会提到。

- 访问元素

指定下标 $i$ 访问元素。

先在大链表上找到节点 $i$ 位于哪一个小链表，只需要从链头开始扫一遍，根据小链表的 siz 确定（一般来说会维护一个小链表中的节点数 siz），复杂度为大链表节点数 $O(\sqrt n)$。

然后进入小链表，从前到后扫一遍找到对应元素，复杂度为小链表节点数 $O(\sqrt n)$。下图是找到节点 $11$ 的过程示意图：

png

这样就把访问的复杂度均衡到了 $O(\sqrt n)$。

- 插入/删除单个元素

某些题对块的大小要求不严格（或者数据水 :(），就可以直接先找到插入的位置，然后直接在该位置插入。

png

但是显然不建议这样写，如果在某个小链表内插入太多，就会破坏 $\sqrt n$ 的性质。比较正确的写法应该是在该位置插入后，若当前小链表的点数超过 $\sqrt n$，则将末尾元素移到下一个小链表的开头，一直移动直到每个链表的点数都不超过 $\sqrt n$。

找到插入位置 $O(\sqrt n)$，在指定小链表内插入 $O(1)$，将小链表链尾移动共 $O(\sqrt n)$ 次，每次 $O(1)$；总复杂度 $O(\sqrt n)$。

就像下面这样：
png

删除同理，删掉元素后，将后面小链表的链头依次接到上一个小链表链尾。

- 插入一段元素

当然保证了插入元素的总个数是 $O(n)$ 级别的。不用一个个插入了，常数大……

先找到插入位置，判断对应小链表中能容纳多少点，先分出前面能容纳的点插入小链表，剩下的点 $\sqrt n$ 分块，满的 $\sqrt n$ 大小的块直接作为一个小链表插入大链表中，剩下的点依次插入。

说起来比较抽象，不如看图：
png

所有插入的总复杂度显然 $O(n\sqrt n)$

# 源代码

> Linked 例题 CF455D

点击展开/折叠 例题题面

给定长度为 $N(N\le100000)$ 的序列 $a$，支持两种操作：

  • 1 l r 将区间 $l$ 到 $r$ 依次向右移动一位，$a_r$ 移动到 $l$；
  • 2 l r k 询问区间 $[l,r]$ 中数字 $k$ 的出现次数。

Hint. 这道题只需要单点插入删除。

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+10,BL=320,MOD=500009;
#define ci int

inline int Read(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r;
}

struct HASHTABLE{
	int val[N],key[N],nxt[N],head[MOD],pol[N+3],npol;
	HASHTABLE(){for(int i=1;i<N;i++) pol[++npol]=i;}
	void Modify(ci id,ci num,ci del){
		int nkey=id*N+num,nt=nkey%MOD,las=-1;
		for(int it=head[nt];it;it=nxt[it])
			if(key[it]==nkey){
				val[it]+=del;
				if(!val[it]){
					pol[++npol]=it;
					if(~las) nxt[las]=nxt[it];
					else head[nt]=nxt[it];
				}
				return;
			}
			else las=it;
		if(del>0){
			int now=pol[npol--];
			nxt[now]=head[nt],key[now]=nkey,val[now]=del;
			head[nt]=now;
		}
	}
	int Query(ci id,ci num){
		int nkey=id*N+num,nt=nkey%MOD;
		for(int it=head[nt];it;it=nxt[it])
			if(key[it]==nkey)
				return val[it];
		return 0;
	}
}Ha;

struct NODE{int key,nxt,pre;}nod[N+2*BL];
int nnod,n,m,q;

struct LIST{
	int st,ed,siz,id;
	void Build(ci i){
		siz=0,id=i;
		st=++nnod,ed=++nnod;
		nod[st].nxt=ed,nod[ed].pre=st;
	}
	void Insert(ci now,ci pre){
		//printf("! %d\n",pre);
		int nxt=nod[pre].nxt;
		nod[pre].nxt=nod[nxt].pre=now;
		nod[now].pre=pre,nod[now].nxt=nxt;
		//printf("%d <- %d -> %d\n",pre,now,nxt);
		Ha.Modify(id,nod[now].key,1);
		siz++;
	}
	void Delete(ci now){
		nod[nod[now].pre].nxt=nod[now].nxt;
		nod[nod[now].nxt].pre=nod[now].pre;
		Ha.Modify(id,nod[now].key,-1);
		siz--;
	}
	void PushFront(ci now){Insert(now,st);}
	void PushBack(ci now){Insert(now,nod[ed].pre);}
	void PopBack(){
		if(!siz) return;
		Delete(nod[ed].pre);
	}
	void PopFront(){
		if(!siz) return;
		Delete(nod[st].nxt);
	}
	int Back(){return siz? nod[ed].pre:0;}
	void Print(){
		int it=nod[st].nxt;printf("!");
		while(it!=ed){
			printf(" %d",nod[it].key);
			it=nod[it].nxt;
		}
		printf("\n");
	}
}Li[BL];

void Find(int pos,int &A,int &B){
	A=1;B=0;
	while(Li[A].siz<pos) pos-=Li[A++].siz;
	B=Li[A].st;
	while(pos--) B=nod[B].nxt;
}
int main(){
	nnod=n=Read(),m=n/BL+bool(n%BL);
	for(int i=1;i<=m;i++) Li[i].Build(i);
	for(int i=1;i<=n;i++){
		nod[i].key=Read();
		Li[i/BL+bool(i%BL)].PushBack(i);
	}
	q=Read();
	int lasans=0;
	while(q--){
		int cmd=Read(),L=(Read()+lasans-1)%n+1,R=(Read()+lasans-1)%n+1;
		if(L>R) swap(L,R);
		int Lblk,Lpos,Rblk,Rpos;
		Find(L,Lblk,Lpos),Find(R,Rblk,Rpos);
		if(cmd==1){
			if(Lblk==Rblk){
				Li[Lblk].Delete(Rpos);
				Li[Lblk].Insert(Rpos,nod[Lpos].pre);
			}
			else{
				Li[Rblk].Delete(Rpos);
				Li[Lblk].Insert(Rpos,nod[Lpos].pre);
				for(int i=Lblk+1;i<=Rblk;i++){
					int it=Li[i-1].Back();
					Li[i-1].PopBack();
					Li[i].PushFront(it);
				}
			}
			//Li[1].Print();
		}
		else{
			int key=(Read()+lasans-1)%n+1;
			lasans=0;
			if(Lblk==Rblk){
				for(int it=Lpos;it!=Rpos;it=nod[it].nxt)
					lasans+=nod[it].key==key;
				lasans+=nod[Rpos].key==key;
			}
			else{
				for(int it=Lpos;it!=Li[Lblk].ed;it=nod[it].nxt)
					lasans+=nod[it].key==key;
				for(int it=Rpos;it!=Li[Rblk].st;it=nod[it].pre)
					lasans+=nod[it].key==key;
				for(int i=Lblk+1;i<Rblk;i++)
					lasans+=Ha.Query(i,key);
			}
			printf("%d\n",lasans);
		}
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 忆墨-网易云