-
Notifications
You must be signed in to change notification settings - Fork 2
/
vol1.toc
298 lines (298 loc) · 23.3 KB
/
vol1.toc
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
\contentsline {chapter}{Preface}{i}{chapter*.2}
\contentsline {section}{\numberline {0.1}Acknowledgement}{i}{section.0.1}
\contentsline {section}{\numberline {0.2}Build History}{i}{section.0.2}
\contentsline {part}{I\hspace {1em}Fundamental}{1}{part.1}
\contentsline {chapter}{\numberline {1}JAVA(详见附录琨神模板)}{3}{chapter.1}
\contentsline {section}{\numberline {1.1}代码框架}{3}{section.1.1}
\contentsline {section}{\numberline {1.2}String}{3}{section.1.2}
\contentsline {section}{\numberline {1.3}BigInteger}{3}{section.1.3}
\contentsline {section}{\numberline {1.4}BigDecimal}{3}{section.1.4}
\contentsline {section}{\numberline {1.5}分数 Fraction}{3}{section.1.5}
\contentsline {chapter}{\numberline {2}Technology}{7}{chapter.2}
\contentsline {section}{\numberline {2.1}代码框架}{7}{section.2.1}
\contentsline {section}{\numberline {2.2}手动扩栈}{9}{section.2.2}
\contentsline {section}{\numberline {2.3}输出格式控制}{9}{section.2.3}
\contentsline {subsection}{\numberline {2.3.1}C}{9}{subsection.2.3.1}
\contentsline {subsection}{\numberline {2.3.2}C++}{9}{subsection.2.3.2}
\contentsline {section}{\numberline {2.4}输入输出优化}{10}{section.2.4}
\contentsline {subsection}{\numberline {2.4.1}输入整数(正/负)}{10}{subsection.2.4.1}
\contentsline {subsection}{\numberline {2.4.2}输出整数}{10}{subsection.2.4.2}
\contentsline {chapter}{\numberline {3}Standard Templete Library(详见附录琨神模板)}{11}{chapter.3}
\contentsline {section}{\numberline {3.1}vector---数组/向量}{11}{section.3.1}
\contentsline {section}{\numberline {3.2}list---表}{11}{section.3.2}
\contentsline {section}{\numberline {3.3}string---字符串}{11}{section.3.3}
\contentsline {subsubsection}{将一个字符串截断}{11}{section.3.3}
\contentsline {subsubsection}{字符串转int, double}{12}{section.3.3}
\contentsline {section}{\numberline {3.4}map/multimap--- 映射/多重映射}{12}{section.3.4}
\contentsline {section}{\numberline {3.5}queue---队列}{13}{section.3.5}
\contentsline {section}{\numberline {3.6}deque---双向队列}{13}{section.3.6}
\contentsline {section}{\numberline {3.7}stack---栈}{13}{section.3.7}
\contentsline {section}{\numberline {3.8}priority\_queue--- 优先队列/最大堆}{13}{section.3.8}
\contentsline {section}{\numberline {3.9}set/multiset--- 集合/多重集合}{13}{section.3.9}
\contentsline {section}{\numberline {3.10}algorithm---算法}{14}{section.3.10}
\contentsline {chapter}{\numberline {4}Attention}{15}{chapter.4}
\contentsline {section}{\numberline {4.1}Tips}{15}{section.4.1}
\contentsline {section}{\numberline {4.2}Error}{15}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}Compile Error}{15}{subsection.4.2.1}
\contentsline {subsection}{\numberline {4.2.2}Runtime Error}{15}{subsection.4.2.2}
\contentsline {subsection}{\numberline {4.2.3}Time Limit Exceeded}{16}{subsection.4.2.3}
\contentsline {section}{\numberline {4.3}Debug Technology}{16}{section.4.3}
\contentsline {part}{II\hspace {1em}Mathematics}{17}{part.2}
\contentsline {chapter}{\numberline {5}Basic}{19}{chapter.5}
\contentsline {section}{\numberline {5.1}高精度算法}{19}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}大整数类 From kuangbin}{19}{subsection.5.1.1}
\contentsline {subsection}{\numberline {5.1.2}大整数类}{26}{subsection.5.1.2}
\contentsline {subsection}{\numberline {5.1.3}高精度FFT乘法($O(N\qopname \relax o{lg}N)$)}{31}{subsection.5.1.3}
\contentsline {section}{\numberline {5.2}统计x(二进制)中1的个数(未知复杂度)}{34}{section.5.2}
\contentsline {section}{\numberline {5.3}二进制生成子集($O(2^N)$)}{35}{section.5.3}
\contentsline {chapter}{\numberline {6}Computation Mathematics}{37}{chapter.6}
\contentsline {section}{\numberline {6.1}计算中序表达式($O(n)$)}{37}{section.6.1}
\contentsline {section}{\numberline {6.2}快速幂取模($O(\qopname \relax o{lg}n)$)}{39}{section.6.2}
\contentsline {section}{\numberline {6.3}二分法：单调函数($O(\qopname \relax o{lg}(nf(n)))$)}{39}{section.6.3}
\contentsline {section}{\numberline {6.4}迭代法(略)}{40}{section.6.4}
\contentsline {section}{\numberline {6.5}三分法：凸性函数($O(\qopname \relax o{lg}(nf(n)))$)}{40}{section.6.5}
\contentsline {section}{\numberline {6.6}解线性方程组}{41}{section.6.6}
\contentsline {subsection}{\numberline {6.6.1}LU 分解(方阵)($O(N^3)$)(优于高斯消元)}{41}{subsection.6.6.1}
\contentsline {subsection}{\numberline {6.6.2}高斯消元($O(N^3)$)}{42}{subsection.6.6.2}
\contentsline {subsubsection}{多功能复杂版}{42}{subsection.6.6.2}
\contentsline {subsubsection}{kuangbin版}{46}{subsection.6.6.2}
\contentsline {subsubsection}{简化版(判是否有解，变上三角矩阵)}{47}{subsection.6.6.2}
\contentsline {subsubsection}{JAVA版}{48}{subsection.6.6.2}
\contentsline {section}{\numberline {6.7}解模线性方程或方程组(未知复杂度)}{52}{section.6.7}
\contentsline {section}{\numberline {6.8}定积分计算}{53}{section.6.8}
\contentsline {subsection}{\numberline {6.8.1}自适应辛普森}{53}{subsection.6.8.1}
\contentsline {subsection}{\numberline {6.8.2}Romberg}{54}{subsection.6.8.2}
\contentsline {section}{\numberline {6.9}多项式求根: 牛顿法}{56}{section.6.9}
\contentsline {section}{\numberline {6.10}周期性方程: 追赶法}{57}{section.6.10}
\contentsline {section}{\numberline {6.11}线性规划(单纯形法)}{58}{section.6.11}
\contentsline {section}{\numberline {6.12}快速傅立叶变换}{62}{section.6.12}
\contentsline {section}{\numberline {6.13}随机算法}{62}{section.6.13}
\contentsline {section}{\numberline {6.14}0/1 分数规划}{62}{section.6.14}
\contentsline {subsection}{\numberline {6.14.1}Theorm}{62}{subsection.6.14.1}
\contentsline {subsection}{\numberline {6.14.2}Dinkelbach算法($O(\qopname \relax o{lg}(nM))$)}{62}{subsection.6.14.2}
\contentsline {subsection}{\numberline {6.14.3}二分法}{63}{subsection.6.14.3}
\contentsline {section}{\numberline {6.15}迭代逼近}{63}{section.6.15}
\contentsline {section}{\numberline {6.16}矩阵快速幂($O(\qopname \relax o{lg}n)$)}{63}{section.6.16}
\contentsline {chapter}{\numberline {7}Combinatorics}{65}{chapter.7}
\contentsline {section}{\numberline {7.1}排列数}{65}{section.7.1}
\contentsline {section}{\numberline {7.2}组合数}{65}{section.7.2}
\contentsline {subsection}{\numberline {7.2.1}打印组合数表}{65}{subsection.7.2.1}
\contentsline {subsection}{\numberline {7.2.2}Theorm}{65}{subsection.7.2.2}
\contentsline {section}{\numberline {7.3}鸽笼原理和Ramsey 定理}{66}{section.7.3}
\contentsline {subsection}{\numberline {7.3.1}鸽笼原理}{66}{subsection.7.3.1}
\contentsline {subsubsection}{基本}{66}{subsection.7.3.1}
\contentsline {subsubsection}{加强}{66}{subsection.7.3.1}
\contentsline {subsubsection}{平均定理}{66}{subsection.7.3.1}
\contentsline {subsection}{\numberline {7.3.2}Ramsey 定理}{66}{subsection.7.3.2}
\contentsline {subsubsection}{定理}{66}{subsection.7.3.2}
\contentsline {subsubsection}{Ramsey数}{66}{subsection.7.3.2}
\contentsline {subsubsection}{Ramsey 数表}{66}{subsection.7.3.2}
\contentsline {section}{\numberline {7.4}常用的公式和数}{66}{section.7.4}
\contentsline {subsection}{\numberline {7.4.1}Sum of Reciprocal(1/n) Approximation}{66}{subsection.7.4.1}
\contentsline {subsection}{\numberline {7.4.2}生成Gray码}{66}{subsection.7.4.2}
\contentsline {subsection}{\numberline {7.4.3}Catalan Number}{67}{subsection.7.4.3}
\contentsline {subsubsection}{Theorm}{67}{subsection.7.4.3}
\contentsline {subsubsection}{应用}{67}{subsection.7.4.3}
\contentsline {subsection}{\numberline {7.4.4}Lucas Number}{67}{subsection.7.4.4}
\contentsline {subsection}{\numberline {7.4.5}Stirling Number}{68}{subsection.7.4.5}
\contentsline {subsubsection}{第一类}{68}{subsection.7.4.5}
\contentsline {subsubsection}{第二类}{68}{subsection.7.4.5}
\contentsline {subsection}{\numberline {7.4.6}Bell Number}{69}{subsection.7.4.6}
\contentsline {subsection}{\numberline {7.4.7}Farey Sequence(法雷序列)}{69}{subsection.7.4.7}
\contentsline {subsubsection}{性质}{69}{subsection.7.4.7}
\contentsline {subsubsection}{递归}{70}{subsection.7.4.7}
\contentsline {subsubsection}{非递归}{70}{subsection.7.4.7}
\contentsline {subsection}{\numberline {7.4.8}五角形数定理(Function Partion P)}{70}{subsection.7.4.8}
\contentsline {subsection}{\numberline {7.4.9}折线划分平面}{71}{subsection.7.4.9}
\contentsline {section}{\numberline {7.5}P$\mathaccentV {acute}013{o}$lya Counting}{71}{section.7.5}
\contentsline {subsection}{\numberline {7.5.1}Burnside引理($O(nsp)$)}{71}{subsection.7.5.1}
\contentsline {subsubsection}{共轭类}{71}{subsection.7.5.1}
\contentsline {subsubsection}{k不动置换类}{71}{subsection.7.5.1}
\contentsline {subsubsection}{等价类}{72}{subsection.7.5.1}
\contentsline {subsubsection}{Burnside 引理}{72}{subsection.7.5.1}
\contentsline {subsection}{\numberline {7.5.2}P$\mathaccentV {acute}013{o}$lya Counting($O(sp)$)}{72}{subsection.7.5.2}
\contentsline {subsection}{\numberline {7.5.3}求置换的循环节}{72}{subsection.7.5.3}
\contentsline {section}{\numberline {7.6}生成函数}{73}{section.7.6}
\contentsline {section}{\numberline {7.7}离散变换与反演}{73}{section.7.7}
\contentsline {chapter}{\numberline {8}Game Theory}{75}{chapter.8}
\contentsline {section}{\numberline {8.1}Basic Game}{75}{section.8.1}
\contentsline {subsection}{\numberline {8.1.1}Bash Game}{75}{subsection.8.1.1}
\contentsline {subsection}{\numberline {8.1.2}Wythoff Game}{75}{subsection.8.1.2}
\contentsline {paragraph}{模板}{75}{subsection.8.1.2}
\contentsline {subsection}{\numberline {8.1.3}翻硬币游戏}{76}{subsection.8.1.3}
\contentsline {subsection}{\numberline {8.1.4}Green Hackenbush}{76}{subsection.8.1.4}
\contentsline {subsubsection}{链删边}{76}{subsection.8.1.4}
\contentsline {subsubsection}{树删边}{76}{subsection.8.1.4}
\contentsline {subsubsection}{局部连通图删边}{76}{subsection.8.1.4}
\contentsline {subsubsection}{无向图删边}{76}{subsection.8.1.4}
\contentsline {section}{\numberline {8.2}简单取子游戏}{76}{section.8.2}
\contentsline {subsection}{\numberline {8.2.1}游戏模型}{76}{subsection.8.2.1}
\contentsline {subsubsection}{游戏定义}{76}{subsection.8.2.1}
\contentsline {subsubsection}{必败点和必胜点(P 点 \& N 点)}{76}{Item.26}
\contentsline {subsubsection}{必败(必胜)点属性}{76}{Item.26}
\contentsline {subsubsection}{算法}{77}{Item.29}
\contentsline {subsection}{\numberline {8.2.2}NIM 取石子游戏}{77}{subsection.8.2.2}
\contentsline {subsubsection}{NIM-SUM 定义}{77}{subsection.8.2.2}
\contentsline {subsubsection}{NIM-SUM 定理}{77}{subsection.8.2.2}
\contentsline {section}{\numberline {8.3}Sprague-Grundy 理论}{77}{section.8.3}
\contentsline {subsection}{\numberline {8.3.1}游戏定义}{77}{subsection.8.3.1}
\contentsline {subsubsection}{基本版}{77}{subsection.8.3.1}
\contentsline {subsubsection}{加强版}{77}{subsection.8.3.1}
\contentsline {subsection}{\numberline {8.3.2}Sprague-Grundy 函数}{77}{subsection.8.3.2}
\contentsline {subsubsection}{MEX(minimal excludant) 运算}{77}{subsection.8.3.2}
\contentsline {subsubsection}{Sprague-Grundy 函数定义}{77}{subsection.8.3.2}
\contentsline {subsubsection}{Sprague-Grundy 函数特点}{78}{subsection.8.3.2}
\contentsline {subsection}{\numberline {8.3.3}游戏模型}{78}{subsection.8.3.3}
\contentsline {subsubsection}{基本版}{78}{subsection.8.3.3}
\contentsline {subsubsection}{加强版}{78}{subsection.8.3.3}
\contentsline {subsection}{\numberline {8.3.4}算法和模板}{78}{subsection.8.3.4}
\contentsline {subsubsection}{一个求MEX 的模板}{78}{subsection.8.3.4}
\contentsline {chapter}{\numberline {9}Number Theory(更多详见附录郭思瑶模板)}{81}{chapter.9}
\contentsline {section}{\numberline {9.1}GCD}{81}{section.9.1}
\contentsline {subsection}{\numberline {9.1.1}Theorm}{81}{subsection.9.1.1}
\contentsline {subsection}{\numberline {9.1.2}欧几里得算法}{81}{subsection.9.1.2}
\contentsline {subsubsection}{思想}{81}{subsection.9.1.2}
\contentsline {subsubsection}{递归($O(\qopname \relax o{lg}n)$)}{81}{Item.41}
\contentsline {subsubsection}{非递归($O(\qopname \relax o{lg}n)$)}{82}{Item.41}
\contentsline {subsection}{\numberline {9.1.3}拓展欧几里得算法}{82}{subsection.9.1.3}
\contentsline {subsubsection}{思想}{82}{subsection.9.1.3}
\contentsline {subsubsection}{递归}{82}{Item.43}
\contentsline {subsubsection}{非递归}{83}{Item.43}
\contentsline {section}{\numberline {9.2}LCM}{83}{section.9.2}
\contentsline {section}{\numberline {9.3}约数}{83}{section.9.3}
\contentsline {subsection}{\numberline {9.3.1}求约数的个数}{83}{subsection.9.3.1}
\contentsline {subsubsection}{Theorm}{83}{subsection.9.3.1}
\contentsline {subsubsection}{Algorithm}{83}{subsection.9.3.1}
\contentsline {subsection}{\numberline {9.3.2}求n的所有约数之和(${O(\sqrt {N})}$)}{83}{subsection.9.3.2}
\contentsline {subsubsection}{思想}{83}{subsection.9.3.2}
\contentsline {subsubsection}{时间复杂度}{83}{subsection.9.3.2}
\contentsline {subsubsection}{程序}{83}{subsection.9.3.2}
\contentsline {section}{\numberline {9.4}欧拉函数PHI(x)}{84}{section.9.4}
\contentsline {subsection}{\numberline {9.4.1}欧拉函数PHI(x) 定义}{84}{subsection.9.4.1}
\contentsline {subsection}{\numberline {9.4.2}计算PHI(n)($O(N)$)}{84}{subsection.9.4.2}
\contentsline {subsection}{\numberline {9.4.3}打印PHI(n) 表($O(N\sqrt {N})$)}{84}{subsection.9.4.3}
\contentsline {subsection}{\numberline {9.4.4}PHI(x) 应用}{85}{subsection.9.4.4}
\contentsline {section}{\numberline {9.5}打印素数表($O(\sqrt {N})$)}{85}{section.9.5}
\contentsline {section}{\numberline {9.6}分解质因数($O(\sqrt {N})$)}{85}{section.9.6}
\contentsline {subsection}{\numberline {9.6.1}分解质因数(无素数表版)}{85}{subsection.9.6.1}
\contentsline {subsection}{\numberline {9.6.2}分解质因数(素数表版,适合批量)}{86}{subsection.9.6.2}
\contentsline {section}{\numberline {9.7}求$n!$被p(素数)整除的p 的个数}{87}{section.9.7}
\contentsline {section}{\numberline {9.8}Primitive Root $||$ 费马小定理}{88}{section.9.8}
\contentsline {subsection}{\numberline {9.8.1}Theorm}{88}{subsection.9.8.1}
\contentsline {paragraph}{费马小定理}{88}{subsection.9.8.1}
\contentsline {paragraph}{Primitive Root(原根)}{88}{subsection.9.8.1}
\contentsline {subsection}{\numberline {9.8.2}求Primitive Root(未知复杂度)}{88}{subsection.9.8.2}
\contentsline {section}{\numberline {9.9}同余乘：避免乘法溢出(未知复杂度)}{89}{section.9.9}
\contentsline {chapter}{\numberline {10}Computational Geometry(详见附录詹钰模板)}{91}{chapter.10}
\contentsline {section}{\numberline {10.1}二维几何定义}{91}{section.10.1}
\contentsline {subsection}{\numberline {10.1.1}常量}{91}{subsection.10.1.1}
\contentsline {subsection}{\numberline {10.1.2}常用}{91}{subsection.10.1.2}
\contentsline {subsection}{\numberline {10.1.3}点(Point2D)}{92}{subsection.10.1.3}
\contentsline {subsection}{\numberline {10.1.4}线段(Segment2D)}{94}{subsection.10.1.4}
\contentsline {subsection}{\numberline {10.1.5}直线(Line2D)}{94}{subsection.10.1.5}
\contentsline {subsection}{\numberline {10.1.6}圆(Circle)}{95}{subsection.10.1.6}
\contentsline {subsection}{\numberline {10.1.7}多边形(POLYGON)}{96}{subsection.10.1.7}
\contentsline {subsection}{\numberline {10.1.8}凸包(CONVEX2D)}{96}{subsection.10.1.8}
\contentsline {section}{\numberline {10.2}二维几何基本操作}{96}{section.10.2}
\contentsline {subsection}{\numberline {10.2.1}得到直线上一点(GetPointOnLine)}{96}{subsection.10.2.1}
\contentsline {subsection}{\numberline {10.2.2}两点构造直线(MakeLine2D)}{96}{subsection.10.2.2}
\contentsline {subsection}{\numberline {10.2.3}构造两点的中垂线(MidPerpLine2D)}{96}{subsection.10.2.3}
\contentsline {subsection}{\numberline {10.2.4}点是否在线段上(PointOnSeg2D)}{97}{subsection.10.2.4}
\contentsline {subsection}{\numberline {10.2.5}判断直线相交(LineLineIntersect2D)}{97}{subsection.10.2.5}
\contentsline {subsection}{\numberline {10.2.6}判断线段相交(SegIntersect2D)}{97}{subsection.10.2.6}
\contentsline {subsection}{\numberline {10.2.7}三点夹角(GetAnglePoint2D)}{98}{subsection.10.2.7}
\contentsline {subsection}{\numberline {10.2.8}点关于直线的对称点(PointSymmetryOnLine2D)}{98}{subsection.10.2.8}
\contentsline {subsection}{\numberline {10.2.9}反射方向(ReflectDir)}{99}{subsection.10.2.9}
\contentsline {subsection}{\numberline {10.2.10}点到直线距离(PointToLine2D)}{99}{subsection.10.2.10}
\contentsline {subsection}{\numberline {10.2.11}点到线段距离(PointToSegment2D)}{99}{subsection.10.2.11}
\contentsline {subsection}{\numberline {10.2.12}点在直线上的投影(GetLineProjection)}{99}{subsection.10.2.12}
\contentsline {subsection}{\numberline {10.2.13}线段与线段距离(SegmentToSegment2D)}{99}{subsection.10.2.13}
\contentsline {subsection}{\numberline {10.2.14}点到线段最短距离(PointToSegment2D)}{100}{subsection.10.2.14}
\contentsline {subsection}{\numberline {10.2.15}直线与直线距离(LineToLine2D)}{101}{subsection.10.2.15}
\contentsline {subsection}{\numberline {10.2.16}直线关于点对称(LineSymmetryOnPoint2D)}{101}{subsection.10.2.16}
\contentsline {subsection}{\numberline {10.2.17}直线与直线的夹角(LineLineArc)}{101}{subsection.10.2.17}
\contentsline {subsection}{\numberline {10.2.18}直线l1逆时针转到l2的角度(LineLineRotArc)}{102}{subsection.10.2.18}
\contentsline {subsection}{\numberline {10.2.19}直线关于直线对称(LineSymmetryOnLine2D)}{102}{subsection.10.2.19}
\contentsline {subsection}{\numberline {10.2.20}直线与圆的交点(CircleLineIntersect)}{102}{subsection.10.2.20}
\contentsline {subsection}{\numberline {10.2.21}三点非共线直线确定圆(PointMakeCircle2D)}{103}{subsection.10.2.21}
\contentsline {subsection}{\numberline {10.2.22}圆上的点p与弧ab的位置关系(PointOnArc2D)}{103}{subsection.10.2.22}
\contentsline {subsection}{\numberline {10.2.23}两圆交点(CirCirIntersect)}{104}{subsection.10.2.23}
\contentsline {subsection}{\numberline {10.2.24}弓形的面积}{104}{subsection.10.2.24}
\contentsline {subsection}{\numberline {10.2.25}两圆/圆环的面积交和并(CircleUnionArea, CircleCommonArea)}{104}{subsection.10.2.25}
\contentsline {subsection}{\numberline {10.2.26}多圆的面积交和并(CirclesUnionArea,CirclesCommonArea)}{105}{subsection.10.2.26}
\contentsline {subsection}{\numberline {10.2.27}求圆外一点到圆的两个切点(OutTangentPoint)}{110}{subsection.10.2.27}
\contentsline {subsection}{\numberline {10.2.28}多边形有向面积(PolyArea)}{110}{subsection.10.2.28}
\contentsline {subsection}{\numberline {10.2.29}多边形重心(PolyCenter)}{111}{subsection.10.2.29}
\contentsline {subsection}{\numberline {10.2.30}点与多边形位置关系(PointInPolygon)}{111}{subsection.10.2.30}
\contentsline {subsection}{\numberline {10.2.31}半平面求交}{112}{subsection.10.2.31}
\contentsline {subsection}{\numberline {10.2.32}}{112}{subsection.10.2.32}
\contentsline {subsection}{\numberline {10.2.33}}{112}{subsection.10.2.33}
\contentsline {subsection}{\numberline {10.2.34}}{112}{subsection.10.2.34}
\contentsline {subsection}{\numberline {10.2.35}}{112}{subsection.10.2.35}
\contentsline {subsection}{\numberline {10.2.36}}{112}{subsection.10.2.36}
\contentsline {subsection}{\numberline {10.2.37}}{112}{subsection.10.2.37}
\contentsline {subsection}{\numberline {10.2.38}}{113}{subsection.10.2.38}
\contentsline {section}{\numberline {10.3}二维几何算法}{113}{section.10.3}
\contentsline {subsection}{\numberline {10.3.1}平面最近点对($O(N\qopname \relax o{lg}N)$)}{113}{subsection.10.3.1}
\contentsline {subsection}{\numberline {10.3.2}最小圆覆盖点($O(N)$)}{114}{subsection.10.3.2}
\contentsline {section}{\numberline {10.4}三维几何定义}{115}{section.10.4}
\contentsline {subsection}{\numberline {10.4.1}}{115}{subsection.10.4.1}
\contentsline {section}{\numberline {10.5}三维几何算法}{116}{section.10.5}
\contentsline {subsection}{\numberline {10.5.1}}{116}{subsection.10.5.1}
\contentsline {part}{III\hspace {1em}Data Structure}{117}{part.3}
\contentsline {chapter}{\numberline {11}基本数据结构}{119}{chapter.11}
\contentsline {section}{\numberline {11.1}队列}{119}{section.11.1}
\contentsline {section}{\numberline {11.2}堆}{120}{section.11.2}
\contentsline {section}{\numberline {11.3}并查集}{121}{section.11.3}
\contentsline {subsection}{\numberline {11.3.1}扩展+异或(la 4487)}{121}{subsection.11.3.1}
\contentsline {subsection}{\numberline {11.3.2}元素的删除与计数}{125}{subsection.11.3.2}
\contentsline {subsection}{\numberline {11.3.3}权值排序+维护根(长春区域赛E)}{126}{subsection.11.3.3}
\contentsline {chapter}{\numberline {12}高级数据结构}{129}{chapter.12}
\contentsline {section}{\numberline {12.1}线段树}{129}{section.12.1}
\contentsline {subsection}{\numberline {12.1.1}单值更新}{129}{subsection.12.1.1}
\contentsline {subsection}{\numberline {12.1.2}段操作（整体区间操作）}{131}{subsection.12.1.2}
\contentsline {subsubsection}{成段增减}{131}{subsection.12.1.2}
\contentsline {subsubsection}{成段替换}{133}{subsection.12.1.2}
\contentsline {subsection}{\numberline {12.1.3}hash+成段更新}{134}{subsection.12.1.3}
\contentsline {subsection}{\numberline {12.1.4}区间交并补等}{137}{subsection.12.1.4}
\contentsline {subsection}{\numberline {12.1.5}连续区间合并问题}{139}{subsection.12.1.5}
\contentsline {subsection}{\numberline {12.1.6}扫描线}{141}{subsection.12.1.6}
\contentsline {subsection}{\numberline {12.1.7}重要题目}{146}{subsection.12.1.7}
\contentsline {subsubsection}{LA3938 Ray, Pass me the dishes!}{146}{subsection.12.1.7}
\contentsline {section}{\numberline {12.2}伸展树(SPlay)}{149}{section.12.2}
\contentsline {subsection}{\numberline {12.2.1}SPlay模板一}{149}{subsection.12.2.1}
\contentsline {subsection}{\numberline {12.2.2}SPlay模板二}{160}{subsection.12.2.2}
\contentsline {section}{\numberline {12.3}RMQ}{169}{section.12.3}
\contentsline {chapter}{\numberline {13}字符串}{171}{chapter.13}
\contentsline {section}{\numberline {13.1}KMP}{171}{section.13.1}
\contentsline {subsection}{\numberline {13.1.1}普通KMP}{171}{subsection.13.1.1}
\contentsline {subsection}{\numberline {13.1.2}拓展KMP}{173}{subsection.13.1.2}
\contentsline {section}{\numberline {13.2}后缀数组}{175}{section.13.2}
\contentsline {subsection}{\numberline {13.2.1}后缀数组模板}{175}{subsection.13.2.1}
\contentsline {subsection}{\numberline {13.2.2}倍增算法构造后缀数组}{178}{subsection.13.2.2}
\contentsline {subsection}{\numberline {13.2.3}应用：子串多次出现在多个串中}{180}{subsection.13.2.3}
\contentsline {subsection}{\numberline {13.2.4}应用：不同子串个数}{184}{subsection.13.2.4}
\contentsline {subsection}{\numberline {13.2.5}应用：重复次数最多的连续子串}{185}{subsection.13.2.5}
\contentsline {subsection}{\numberline {13.2.6}应用：最长不重复子串}{190}{subsection.13.2.6}
\contentsline {section}{\numberline {13.3}AC自动机}{193}{section.13.3}
\contentsline {section}{\numberline {13.4}回文串}{196}{section.13.4}
\contentsline {subsection}{\numberline {13.4.1}判回文串}{196}{subsection.13.4.1}
\contentsline {subsubsection}{更改字符，判任意区间是否为回文串(线段树+字符串哈希)(Ural 1989)}{196}{subsection.13.4.1}
\contentsline {subsection}{\numberline {13.4.2}最长回文串}{199}{subsection.13.4.2}
\contentsline {section}{\numberline {13.5}Other}{206}{section.13.5}
\contentsline {subsection}{\numberline {13.5.1}字符串哈希(推荐BKDR)}{206}{subsection.13.5.1}
\contentsline {subsubsection}{字符串哈希算法}{206}{subsection.13.5.1}
\contentsline {paragraph}{普通字符串哈希算法}{206}{subsection.13.5.1}
\contentsline {subsubsection}{$O(N)$预处理$O(1)$查询的字符串哈希}{207}{subsection.13.5.1}
\contentsline {subsection}{\numberline {13.5.2}最小表示法\ \& 最大表示法}{207}{subsection.13.5.2}
\contentsline {subsection}{\numberline {13.5.3}找某个字符串的不同子串的数目($O(N^2)$)}{208}{subsection.13.5.3}
\contentsline {chapter}{\numberline {14}树}{211}{chapter.14}
\contentsline {section}{\numberline {14.1}树的分治}{211}{section.14.1}
\contentsline {subsection}{\numberline {14.1.1}树的重心：POJ 1655 Balancing Art}{211}{subsection.14.1.1}
\contentsline {subsection}{\numberline {14.1.2}树链剖分}{215}{subsection.14.1.2}
\contentsline {subsubsection}{HDU 5029 Relief grain}{215}{subsection.14.1.2}
\contentsline {subsubsection}{SPOJ 375 (更改边值，询问极值)}{219}{subsection.14.1.2}
\contentsline {subsubsection}{POJ 3237 Tree}{223}{subsection.14.1.2}
\contentsline {section}{\numberline {14.2}动态树(LCT)}{228}{section.14.2}
\contentsline {subsection}{\numberline {14.2.1}HDU 4010}{228}{subsection.14.2.1}
\contentsline {subsection}{\numberline {14.2.2}HDU 5002}{234}{subsection.14.2.2}