Nim-ACL

AtCoder Level-Based Library Guide

This page groups Nim-ACL modules by approximate AtCoder color level.

The classification is only a guideline. The difficulty of a problem depends heavily on recognizing the technique and combining it with other ideas.

Level Approximate colors
Beginner Gray, brown, green
Intermediate Cyan, blue
Advanced Yellow and above

Relationship to the official lecture catalog

The beginner/intermediate/advanced levels on this page are Nim-ACL-specific usage categories. They are separate from the official difficulty levels 1–9.

See the AtCoder Algorithm Lectures coverage page for the official cross-reference.

Beginner

Focus on basic transformations, graph traversal, prefix aggregation, and standard data structures.

Area Module Typical use
Array Coordinate Compression Large sparse coordinates
Array Run-Length Encoding Consecutive equal groups
Set MexSet Dynamic mex
Set SortedSet / SortedMap Ordered containers
Graph Functional Graph / Doubling Apply a function many times
String KMP Single-pattern matching
Geometry Geometry facade Basic geometry

Core ACL modules:

import atcoder/dsu
import atcoder/fenwicktree
import atcoder/segtree
import atcoder/modint

Suggested order

  1. Run-Length Encoding
  2. Coordinate Compression
  3. Prefix sums
  4. DSU
  5. Fenwick Tree
  6. Dijkstra
  7. Segment Tree
  8. Functional Graph
  9. KMP

Intermediate

Intermediate problems require selecting a structure based on static/dynamic, online/offline, and algebraic properties.

Range queries

Module Use
Sparse Table Static idempotent queries
Disjoint Sparse Table Static associative queries
FastSet Successor / predecessor
Binary Trie XOR optimization
Wavelet Matrix Rank, frequency, k-th
Mo Offline range queries
Cartesian Tree RMQ and monotonic stack structure

Strings

Module Use
Manacher Palindrome radii
Aho-Corasick Multiple-pattern matching
Minimum Rotation Canonical cyclic rotation
Rolling Hash Substring comparison
Suffix Array Lexicographic substring structure

Trees and DP

Module Use
Rerooting DP Tree DP for every root
Heavy-Light Decomposition Path queries
LCA Ancestor and distance queries

Static and persistent range structures

Module Use
Sqrt Tree Static monoid range products
Persistent Segment Tree Queries over old versions
Euler Tour Convert subtrees to intervals

Advanced

Advanced problems frequently combine offline processing, rollback, tree compression, and graph decomposition.

Dynamic connectivity

Module Use
Rollback DSU Undo DSU merges
Offline Dynamic Connectivity Edge insertion/deletion offline
Partially Persistent DSU Queries about past states

Advanced tree techniques

Module Use
Virtual Tree Compress important vertices
DSU on Tree Subtree frequency queries
Rerooting DP All-root tree DP
Link-Cut Tree Dynamic forests

Undirected graph decomposition

Module Use
Undirected Graph Decomposition Shared low-link interface
Biconnected Components Articulation-based blocks
Two-Edge-Connected Components Bridge-based components
Block-Cut Tree Tree of blocks and articulations

Advanced strings

Module Use
Suffix Automaton Distinct substrings and occurrences
Palindromic Tree Distinct palindromes
Aho-Corasick Automaton DP
Suffix Array / LCP Substring ordering

Advanced mathematics

Module Use
FPS Formal power series
Convolution / NTT Polynomial multiplication
XOR Basis GF(2) linear basis

Quick selection guide

Problem shape Candidate
Large values, few distinct coordinates Coordinate Compression
Apply a mapping k times Functional Graph
Max/min XOR with an element Binary Trie
Representable subset XOR XOR Basis
Multiple patterns Aho-Corasick
Palindrome range checks Manacher
Distinct palindromes Palindromic Tree
Every-root tree DP Rerooting
Subtree frequency queries DSU on Tree
Important vertex subset on a tree Virtual Tree
Offline edge deletion Offline Dynamic Connectivity
Bridges and articulation points Low-link decomposition

Future candidates

High-priority future candidates include: