Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"CodeForces-140C\":[\"New Year Snowmen\",5023,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/140\\\"\\u003eCodeforces Round 100\\u003c/a\\u003e\"],\"CodeForces-617E\":[\"XOR and Favorite Number\",9032,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/617\\\"\\u003eCodeforces Round 340 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-86D\":[\"Powerful array\",14626,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/86\\\"\\u003eYandex.Algorithm 2011: Round 2\\u003c/a\\u003e\"],\"AtCoder-past202212_n\":[\"Sequence and Function\",2,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202212-open\\\"\\u003e第13回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"],\"CodeForces-220B\":[\"Little Elephant and Array\",10465,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/220\\\"\\u003eCodeforces Round 136 (Div. 1)\\u003c/a\\u003e\"],\"CodeForces-940F\":[\"Machine Learning\",2673,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/940\\\"\\u003eCodeforces Round 466 (Div. 2)\\u003c/a\\u003e\"],\"CodeForces-1819B\":[\"The Butcher\",3434,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1819\\\"\\u003eCodeforces Round 866 (Div. 1)\\u003c/a\\u003e\"],\"AtCoder-past202004_e\":[\"Permutation\",1,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/past202004-open\\\"\\u003e第二回 アルゴリズム実技検定 過去問\\u003c/a\\u003e\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"hh2048","updateTime":1695878531000,"title":"W的A题计划 - 数据结构","dislikeCnt":0,"content":"## 并查集\n\n由于本人非常喜欢使用并查集,有很多做法正解可能不是并查集但是我写了、于是就一并列上来了。\n\n并查集算法除了常规意义上的寻找(时间序意义上的)祖先节点、寻找块内最小/最大的节点之外,还可以用极小的时间代价维护连通块内点的数量、边的数量、是否存在自环等等内容。通常意义上我们默认增加“路径压缩”优化,时间复杂度为:查询 $\\mathcal O (1)$ ,合并接近于 $\\mathcal O(\\alpha(n))$ (这里 $\\alpha$ 代表的是反阿克曼函数,一般看作是一个极小的常数);此外还有“启发式合并“优化能够进一步缩短合并花费的时间,然而这会影响上述罗列的最大/最小节点查找,故一般我个人习惯不添加这一优化。\n\n[problem:AtCoder-past202004_e] 并查集找点集大小\n\n## 莫队算法\n\n### 简要讲解\n\n普通莫队:以 $\\mathcal O(N \\sqrt N)$ 的复杂度完成 $Q$ 次询问的离线查询,其中每个分块的大小取 $\\sqrt N\u003d\\sqrt {10^5} \u003d 317$ ,也可以使用 `ceil((double)n / (int)sqrt(n))` 或者 `sqrt(n)` 划分。\n\n带修莫队:以 $\\mathcal O(N^\\frac{5}{3})$ 的复杂度完成 $Q$ 次询问的离线查询,其中每个分块的大小取 $N^\\frac{2}{3}\u003d\\sqrt\\[3]{100000^2}\u003d2154$ (直接取会略快),也可以使用 `pow(n, 0.6666)` 划分。\n\n### 题单\n\n[problem:CodeForces-617E] 普通莫队\n\n[problem:CodeForces-86D] 普通莫队\n\n[problem:CodeForces-220B] 普通莫队\n\n[problem:AtCoder-past202212_n] 普通莫队\n\n[problem:CodeForces-940F] 带修莫队、离散化\n\n## STL与库函数\n\n[problem:CodeForces-1819B] 优先队列+标记、set\n\n[problem:CodeForces-140C] 哈希表、优先队列","threadId":152365,"likeCnt":0,"createTime":1690355835000,"isWorkbook":true,"viewCnt":154,"openness":2,"fav":false,"id":3894,"trustable":false}