USACO Guide Platinum

https://usaco.guide/plat/
Admin
USACO Guide Platinum is an educational resource covering advanced competitive programming topics...
Tokens:47,561
Snippets:348
Trust Score:9.3
Update:11 months ago
Show doc for...
Tokens:
Raw
### Example Usage of Offline 2D BIT in C++

Source: https://usaco.guide/plat/2DRQ_lang=cpp

A C++ code snippet demonstrating the usage of an offline 2D BIT. This example includes necessary headers and defines a `main` function, suggesting how the BIT might be initialized and utilized in a competitive programming context. It relies on standard libraries and potentially custom BIT structures.

```cpp
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;


int main() {


```

--------------------------------

### Full Code Setup for Small-to-Large Merging (C++)

Source: https://usaco.guide/plat/merging

This C++ code provides the basic setup for implementing Small-to-Large Merging. It includes necessary headers, defines a maximum size for nodes, and declares an adjacency list for a tree and an array of sets to store colors for each node. This structure is typical for problems involving tree traversal and set merging.

```cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;

// nodes will be 1-indexed like in the problem
vector<int> adj[MAX_N + 1];

set<int> colors[MAX_N + 1];

// Function to perform small-to-large merging would go here
void merge_sets(int u, int v) {
    // Example: merge colors of child v into parent u
    if (colors[u].size() < colors[v].size()) {
        swap(colors[u], colors[v]);
    }
    for (int color : colors[v]) {
        colors[u].insert(color);
    }
    // Clear the smaller set after merging if necessary
    // colors[v].clear(); 
}

int main() {
    // Example usage: Assume some graph structure and color assignments
    // For demonstration, let's manually populate some data
    
    // Assign colors to nodes
    colors[1].insert(10);
    colors[2].insert(20);
    colors[2].insert(10);
    
    // Add edges (example: 1 is parent of 2)
    adj[1].push_back(2);
    
    // Simulate merging (e.g., after visiting children)
    cout << "Before merging: colors[1] = ";
    for(int c : colors[1]) cout << c << " ";
    cout << ", colors[2] = ";
    for(int c : colors[2]) cout << c << " ";
    cout << endl;

    merge_sets(1, 2);

    cout << "After merging: colors[1] = ";
    for(int c : colors[1]) cout << c << " ";
    cout << ", colors[2] = ";
    for(int c : colors[2]) cout << c << " "; // colors[2] might be empty or swapped
    cout << endl;

    return 0;
}

```

--------------------------------

### Main Function for Path Queries II Example in C++

Source: https://usaco.guide/plat/hld

This C++ code snippet shows the main function structure for a problem likely involving Heavy Light Decomposition and Segment Trees, possibly for path queries. It includes standard competitive programming optimizations like disabling sync with stdio and un-tying cin/cout. It assumes the existence of Segment Tree and HLD implementations.

```cpp
#include <bits/stdc++.h>
using namespace std;


 Code Snippet: Segment Tree (Click to expand) 


 Code Snippet: HLD (Click to expand) 


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);


```

--------------------------------

### Virtual Tree Optimization DP - C++ Setup

Source: https://usaco.guide/plat/VT

This C++ code snippet sets up the basic constants and variables for a competitive programming problem that likely involves virtual tree optimization. It defines maximum array size, logarithm base for binary lifting, and a modulo value. It also declares variables for the number of nodes and an array 'a' to store node properties, often colors or types.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


constexpr int MAX_N = 2e5 + 1;
constexpr int LG = 18;
constexpr int MOD = 998244353;


int n, a[MAX_N];

```

--------------------------------

### SQFREE Application Setup - C++

Source: https://usaco.guide/plat/PIE

This C++ code snippet sets up the necessary variables and includes for the SQFREE problem, which utilizes the inclusion-exclusion principle and Mobius function. It defines the maximum value for the Mobius array and declares the array itself. This is a common setup for problems involving number theory and combinatorics.

```cpp
#include <iostream>
#include <vector>

using namespace std;

const int VALMAX = 1e7;

int mobius[VALMAX];

int main() {
```

--------------------------------

### Sweep Line Implementation (C++)

Source: https://usaco.guide/plat/sweep-line

C++ implementation for a sweep line algorithm. This snippet includes basic setup and a sign function, likely used for geometric calculations within the sweep line approach.

```cpp
#include <bits/stdc++.h>
using namespace std;


long long sweep_line_x;


int sign(long long x) {


```

--------------------------------

### Full C++ Implementation for Small-to-Large Merging

Source: https://usaco.guide/plat/merging_lang=cpp

This C++ code provides a foundational structure for implementing Small-to-Large Merging in a competitive programming context. It includes standard headers, defines a maximum node count, declares an adjacency list for a tree, and initializes an array of sets to store colors for each node. This setup is typical for problems requiring efficient merging of information across tree subtrees.

```cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e5;

// nodes will be 1-indexed like in the problem
vector<int> adj[MAX_N + 1];

set<int> colors[MAX_N + 1];

// Placeholder for the merging logic, typically within a DFS function
void dfs(int u, int p) {
    // Process children recursively
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        
        // Small-to-large merge: merge child's set into current node's set
        if (colors[u].size() < colors[v].size()) {
            swap(colors[u], colors[v]);
        }
        for (int color : colors[v]) {
            colors[u].insert(color);
        }
        // Clear the child's set after merging to save memory if needed
        colors[v].clear(); 
    }
    // Add the current node's own color (assuming it has one)
    // colors[u].insert(node_color[u]); 
}

int main() {
    // Example Usage (not a complete program):
    // Build the tree (adj list)
    // Initialize colors for each node
    // Call dfs(1, 0) or appropriate root
    
    return 0;
}
```

--------------------------------

### Main Function for Optimized DP - C++

Source: https://usaco.guide/plat/sqrt_lang=cpp

Sets up the main function for an optimized dynamic programming solution. It reads input values `n` and the array `a`, and initializes necessary data structures like the `dp` array and the `s` table for prefix sums.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MOD = 998244353;


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }


```

--------------------------------

### Main Function for Combined Algorithms - C++

Source: https://usaco.guide/plat/sqrt

The main function for a problem that combines DP and prefix sums. It initializes variables, reads input, and sets up the DP array. This serves as the entry point for executing the optimized algorithm.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


const int MOD = 998244353;


int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) { cin >> a[i]; }

```

--------------------------------

### LCA using Euler Tour and Binary Lifting

Source: https://usaco.guide/plat/binary-jump_lang=cpp

Implements LCA calculation using an Euler tour of the tree. It computes start and end times for nodes and utilizes binary jumping to find ancestors. The time complexity is O((N+Q)logN).

```cpp
#include <cmath>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

class Tree {
  private:

```

--------------------------------

### Online Static Range Queries using Divide & Conquer (C++)

Source: https://usaco.guide/plat/DC-SRQ_lang=cpp

This C++ code provides an online solution for static range queries using divide and conquer. It precomputes and stores range aggregates in a 2D array `dat` and uses a `mask` array to optimize query lookups. The `divi` function generates these structures. It's suitable for associative operations where `min` is used as an example. Dependencies include standard C++ libraries and a `vi` type (likely std::vector).

```cpp
int n, q;
vi x, ans;


int dat[18][MX], mask[MX];  // 18 = ceil(log2(n))


void divi(int l, int r, int lev) {  // generate dat and mask
	if (l == r) return;
	int m = (l + r) / 2;
	dat[lev][m] = x[m];
	ROF(i, l, m) dat[lev][i] = min(x[i], dat[lev][i + 1]);


```

--------------------------------

### Prefix Sum Array Initialization - C++

Source: https://usaco.guide/plat/sqrt

Initializes a prefix sum array for batch processing. The `build` function sets the first element of the prefix array to 0, which is a common starting point for prefix sum calculations. This is part of a batching strategy to handle updates efficiently.

```cpp
#include <bits/stdc++.h++.h>
using namespace std;


int n, q;
vector<int> arr;
vector<long long> prefix;


/** Build the prefix array for arr */
void build() {
	prefix[0] = 0;

```

--------------------------------

### Vowels Problem - SOS DP Initialization - C++

Source: https://usaco.guide/plat/dp-sos_lang=cpp

This C++ snippet sets up the initial structures for solving the 'Vowels' problem using SOS DP. It includes necessary headers, defines a constant for the maximum number of elements (M), and declares an array 'sos' to store the SOS DP states.

```cpp
#include <iostream>
#include <string>


const int M = 24;
int sos[1 << M];


int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; i++) {

}
```

--------------------------------

### C++ Sweep Line Implementation Snippet

Source: https://usaco.guide/plat/sweep-line_lang=cpp

A basic C++ implementation snippet for sweep line algorithms, likely involving sorting and processing events. It includes standard headers and a 'sign' function.

```cpp
#include <bits/stdc++.h>
using namespace std;


long long sweep_line_x;


int sign(long long x) {

}
```

--------------------------------

### Multidimensional BIT Template in C++

Source: https://usaco.guide/plat/2DRQ_lang=cpp

A C++ template for a multidimensional Binary Indexed Tree (BIT). This generic implementation allows for N-dimensional BITs, useful for problems requiring higher-dimensional range queries.

```cpp
template <class T, int... Ns> struct BIT {
	T val = 0;
	void upd(T v) { val += v; }
	T query() { return val; }
};


template <class T, int N, int... Ns> struct BIT<T, N, Ns...> {
	BIT<T, Ns...> bit[N + 1];
	template <typename... Args> void upd(int pos, Args... args) {
		for (; pos <= N; pos += (pos & -pos)) bit[pos].upd(args...);

```

--------------------------------

### Knapsack Subset Sum with Bitset (C++)

Source: https://usaco.guide/plat/bitsets

This C++ snippet demonstrates how to use a bitset to solve the knapsack subset sum problem. It initializes a bitset, sets the base case for a sum of 0, and then iteratively updates the bitset to represent achievable sums by adding component sizes. The final bitset indicates all possible subset sums.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	init();
	bitset<100001> posi;
	posi[0] = 1;
	for (int t : comps) posi |= posi << t;
	for (int i = 1; i <= n; ++i) cout << posi[i];
	cout << "\n";
}
```

--------------------------------

### Fibonacci Matrix Recurrence

Source: https://usaco.guide/plat/matrix-expo_lang=cpp

Demonstrates the matrix form for calculating Fibonacci numbers. The matrix [1, 1; 1, 0] raised to the power of n relates to Fibonacci numbers F(n+1), F(n), and F(n-1). This is a foundational example for matrix exponentiation in recurrences.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


const ll MOD = 1e9 + 7;


using Matrix = array<array<ll, 2>, 2>;


Matrix mul(Matrix a, Matrix b) {


```

--------------------------------

### Manhattan MST Grid Implementation (C++)

Source: https://usaco.guide/plat/sweep-line

C++ implementation for solving the Manhattan Minimum Spanning Tree problem on a grid. It utilizes Dijkstra's algorithm and pre-defined grid traversals.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int GRID_SZ = 1000;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};


int main() {
	int n;
	cin >> n;


```

--------------------------------

### Knapsack DP with Bitset Optimization

Source: https://usaco.guide/plat/bitsets_lang=cpp

This snippet shows how to use `std::bitset` to optimize a dynamic programming solution for the knapsack problem. It initializes a bitset `posi` where `posi[j] = 1` if a sum of `j` is achievable using a subset of component sizes. The bitset is updated by ORing it with left-shifted versions to represent adding component sizes.

```cpp
#include <bits/stdc++.h>
using namespace std;


// Code Snippet: DSU (Click to expand)


DSU D;
int n, m;
vector<int> comps;


void init() {

}
```

```cpp
#include <bits/stdc++.h>
using namespace std;


// Code Snippet: DSU (Click to expand)


int main() {
	init();
	bitset<100001> posi;
	posi[0] = 1;
	for (int t : comps) posi |= posi << t;
	for (int i = 1; i <= n; ++i) cout << posi[i];
	cout << "\n";
}
```

--------------------------------

### C++ Grid MST Implementation Snippet

Source: https://usaco.guide/plat/sweep-line_lang=cpp

C++ implementation for solving Grid MST problems using Dijkstra's algorithm. It defines grid size and movement directions, suitable for problems where points are on a grid.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int GRID_SZ = 1000;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};


int main() {
	int n;
	cin >> n;

}
```

--------------------------------

### Optimized DP with Prefix Sums for Hop Sugoroku - C++

Source: https://usaco.guide/plat/sqrt_lang=cpp

An optimized dynamic programming solution for Hop Sugoroku that combines direct DP with prefix sums. It uses a 2D array `s` to store prefix sums for different modulo values, improving efficiency for smaller jumps.

```cpp
for (int i = n - 1; i >= 0; i--) {
	dp[i] += s[a[i]][i % a[i]];
	dp[i] %= MOD;


	for (int j = 1; j <= x; j++) {
		s[j][i % j] += dp[i];
		s[j][i % j] %= MOD;
	}
}


```

--------------------------------

### Full Cow Compatibility Solution with Bitsets (C++)

Source: https://usaco.guide/plat/bitsets

This is the complete C++ main function for the cow compatibility problem using bitsets. It first processes flavors to update adjacency lists and then calculates the total compatible pairs by summing the counts of set bits in the adjacency bitsets. It assumes no test case exceeds the HALF limit.

```cpp
int main() {
	input();
	for (int i = 1; i <= 1000000; ++i)
		if (flav[i].size() > 0) {
			B b;
			for (int x : flav[i]) b[x] = 1;
			for (int x : flav[i])
				if (x < HALF) adj[x] |= b;
		}
	for (int i = 0; i < HALF; ++i) ans += adj[i].count();

}
```

--------------------------------

### Cow Compatibility Adjacency Bitset (C++)

Source: https://usaco.guide/plat/bitsets

This C++ code initializes bitsets to represent adjacency between cows based on shared flavors. It iterates through flavors, and for each flavor, it updates the adjacency bitsets of cows sharing that flavor. The final count of compatible pairs is accumulated by summing the set bits in the adjacency bitsets.

```cpp
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef bitset<50000> B;
const int HALF = 25000;


int N;
B adj[HALF];
vector<int> flav[1000001];

int main() {
	input();
	for (int i = 1; i <= 1000000; ++i)
		for (int x : flav[i])
			if (x < HALF)
				for (int y : flav[i]) adj[x][y] = 1;
	for (int i = 0; i < HALF; ++i) ans += adj[i].count();
}
```

--------------------------------

### Batching Structure for Array Updates and Queries - C++

Source: https://usaco.guide/plat/sqrt_lang=cpp

Initializes data structures for batch processing of array updates and queries. It includes a `prefix` array to store prefix sums, which is essential for calculating range sums efficiently. The `build` function initializes the prefix sum array.

```cpp
#include <bits/stdc++.h>
using namespace std;


int n, q;
vector<int> arr;
vector<long long> prefix;


/** Build the prefix array for arr */
void build() {
	prefix[0] = 0;


```

--------------------------------

### Optimized Cow Compatibility Bitset Update (C++)

Source: https://usaco.guide/plat/bitsets

This C++ code snippet optimizes the cow compatibility calculation by using a temporary bitset for each flavor. It iterates through flavors, creates a bitset representing cows with that flavor, and then efficiently updates the adjacency bitsets for cows below HALF using bitwise OR operations.

```cpp
for (int i = 1; i <= 1000000; ++i)
	if (flav[i].size() > 0) {
		B b;
		for (int x : flav[i]) b[x] = 1;
		for (int x : flav[i])
			if (x < HALF) adj[x] |= b;
	}
```

--------------------------------

### Closest Pair: Sweep Line with C++ Set

Source: https://usaco.guide/plat/sweep-line

This C++ code snippet demonstrates the initialization of reading points for the sweep line algorithm. It reads the number of points and then their x and y coordinates, preparing them for further processing within the O(N log N) algorithm.

```cpp
#include <bits/stdc++.h>\nusing namespace std;\n\n\nusing ld = long double;\n\n\nint main() {\n\tint n;\n\twhile (cin >> n && n > 0) {\n\t\tvector<pair<ld, ld>> points(n);\n\t\tfor (auto &p : points) { cin >> p.first >> p.second; }\n\n
```

--------------------------------

### Tarjan's Offline LCA Algorithm

Source: https://usaco.guide/plat/binary-jump_lang=cpp

Implements Tarjan's Offline LCA algorithm which uses DFS and a Disjoint-Set Union-like structure to precompute LCA for multiple queries efficiently. The time complexity is O((N+Q)logN) or O((N+Q)α(N)) depending on DSU implementation.

```cpp
#include <bits/stdc++.h>
using namespace std;

const int MAX = 2e5 + 1;
bool vis[MAX];
int lca[MAX], fa[MAX];
vector<array<int, 2>> adj[MAX], qry[MAX];
int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }
void tarjan(int node) {
	vis[node] = true;

```

--------------------------------

### 2D BIT Implementation in C++

Source: https://usaco.guide/plat/2DRQ_lang=cpp

A C++ implementation of a 2D Fenwick Tree (Binary Indexed Tree) for handling 2D range queries. This implementation uses zero-indexed cells and supports generic types.

```cpp
#include <iostream>
#include <vector>
using namespace std;


/**
 * 2D Fenwick Tree implementation.
 * Note that all cell locations are zero-indexed
 * in this implementation.
 */
template <typename T> class BIT2D {

```

--------------------------------

### Sum Over Subsets DP: Iterating Over Submasks (C++)

Source: https://usaco.guide/plat/dp-sos_lang=cpp

An optimized solution for Sum Over Subsets (SOS) DP that iterates directly over the submasks of each mask x. It uses the property `i = (i - 1) & x` to efficiently generate subsets in reverse order. This reduces the time complexity to O(3^n).

```cpp
vector<int> sos(1 << n);


for (int x = 0; x < (1 << n); x++) {
	sos[x] = a[0];
	// iterate over all subsets of x directly
	for (int i = x; i > 0; i = (i - 1) & x) { sos[x] += a[i]; }
}
```

--------------------------------

### Knapsack DP with Bitsets and Randomization in C++

Source: https://usaco.guide/plat/bitsets_lang=cpp

Addresses the unbounded knapsack problem using dynamic programming optimized with bitsets and a probabilistic approach. It shuffles the input integers randomly and applies a threshold to the DP state to reduce the state space, achieving an O(nX) complexity where X is related to the maximum value and square root of n.

```C++
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

int n, c;
const int Z = 1000000;
mt19937 rng;


int solve() {

```

--------------------------------

### Naive Set Merging (C++)

Source: https://usaco.guide/plat/merging

This code snippet demonstrates a naive approach to merging two sets, `a` and `b`, where elements from `b` are inserted into `a`. This method has a time complexity of O(m log(n+m)) for merging sets of size n and m, leading to O(N^2 log N) in worst-case scenarios.

```cpp
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

int main() {
    std::set<int> a = {1, 3, 5};
    std::set<int> b = {2, 4, 6};
    
    // Naive merging: insert all elements from b into a
    for (int x : b) {
        a.insert(x);
    }
    
    // a now contains {1, 2, 3, 4, 5, 6}
    std::cout << "Merged set a: ";
    for (int x : a) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}
```

--------------------------------

### Initialize Tree and Subtree Size Variables (C++)

Source: https://usaco.guide/plat/centroid

Initializes global variables for tree representation and subtree size calculation. `adj` is an adjacency list for the tree, `n` is the number of nodes, and `subtree_size` will store the size of each subtree.

```cpp
#include <iostream>
#include <vector>


using namespace std;


const int maxn = 200010;


int n;
vector<int> adj[maxn];
int subtree_size[maxn];
```

--------------------------------

### Radial Sweep Event Structure and PI Constant (C++)

Source: https://usaco.guide/plat/sweep-line

C++ implementation for a radial sweep algorithm. It defines a structure for events with type and id, and the mathematical constant PI for angular calculations.

```cpp
#include <bits/stdc++.h>
#define x first
#define y second
typedef long long ll;
using namespace std;


const double PI = 4 * atan(1);


struct Event {
	short type, id;


```

--------------------------------

### Sum Over Subsets DP: Brute Force (C++)

Source: https://usaco.guide/plat/dp-sos_lang=cpp

Implements the brute-force approach for Sum Over Subsets (SOS) DP. It iterates through all possible masks (x) and then through all their subsets (i), summing the values from array 'a'. This has a time complexity of O(4^n), which is inefficient for larger n.

```cpp
vector<int> sos(1 << n);


for (int x = 0; x < (1 << n); x++) {
	// iterate over all other sets and checks whether they're a subset of x
	for (int i = 0; i < (1 << n); i++) {
		if ((i & x) == i) { sos[x] += a[i]; }
	}
}
```

--------------------------------

### N-Dimensional Prefix Sum (SOS DP) Calculation - C++

Source: https://usaco.guide/plat/dp-sos_lang=cpp

Implements the N-dimensional prefix sum using a sweeping algorithm, which is equivalent to the SOS DP. It iterates through each dimension (bit) and accumulates sums for supermasks based on submasks. This is a memory-optimized solution for SOS problems.

```cpp
F = A;


for (int i = 0; i < n; i++) {  // Sweep along the i-th axis
	for (int x = 0; x < (1 << n); x++) {
		if (x & (1 << i))  // If the i-th bit is set, accumulate
			F[x] += F[x ^ (1 << i)];
	}
}
```

--------------------------------

### HLD Class Implementation in C++

Source: https://usaco.guide/plat/hld

This C++ code snippet defines a generic Heavy Light Decomposition (HLD) class. It supports path and subtree operations on a tree, using a Lazy Segment Tree for efficient range updates and queries. Dependencies include a LazySegtree class (not shown).

```cpp
#include <bits/stdc++.h>
using namespace std;


template <class T, bool VALS_IN_EDGES> class HLD {
  private:
	int N, R, tim = 0;  // n, root node, time
	vector<vector<int>> adj;
	vector<int> par, siz, depth, rt, pos;  // parent, size, depth, root, position arrays
	LazySegtree<T> segtree;                // Modify as needed


```

--------------------------------

### Mo's Algorithm C++ Structure for Queries

Source: https://usaco.guide/plat/sqrt_lang=cpp

This C++ code snippet defines a structure for queries, commonly used in Mo's Algorithm. It includes the left and right bounds of the query range and its original index. This structure is essential for sorting and processing queries efficiently.

```cpp
#include <bits/stdc++.h>
using namespace std;


struct Query {
	int l, r, idx;
};


int main() {
	int n;
	cin >> n;


```

--------------------------------

### Dynamic Programming for Hop Sugoroku - C++

Source: https://usaco.guide/plat/sqrt_lang=cpp

Calculates dynamic programming states for the Hop Sugoroku problem. This DP approach iterates backward from the end of the array, updating states based on possible jumps. It uses modular arithmetic to prevent overflow.

```cpp
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--) {
	for (int x = i + a[i]; x <= n; x += a[i]) { dp[i] = (dp[i] + dp[x]) % MOD; }
}


```

--------------------------------

### Binary Jumping Implementation in C++

Source: https://usaco.guide/plat/binary-jump

This C++ code snippet provides an implementation for binary jumping, a technique used for efficiently finding the k-th ancestor of a node in a tree. It utilizes a table to store precomputed ancestors, enabling logarithmic time complexity for queries. The time complexity for this implementation is O((N+Q)logN).

```cpp
#include <cmath>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


class Tree {
  private:


```

--------------------------------

### Tarjan's Offline LCA Algorithm (C++)

Source: https://usaco.guide/plat/binary-jump

Implementation of Tarjan's Offline LCA algorithm in C++. This method utilizes DFS and a Disjoint-Set Union (DSU) data structure to efficiently compute LCAs for multiple queries offline. It requires pre-computation and has a time complexity suitable for competitive programming scenarios.

```cpp
#include <bits/stdc++.h>
using namespace std;


const int MAX = 2e5 + 1;
bool vis[MAX];
int lca[MAX], fa[MAX];
vector<array<int, 2>> adj[MAX], qry[MAX];
int find(int u) { return (fa[u] == u) ? u : fa[u] = find(fa[u]); }
void tarjan(int node) {
	vis[node] = true;

```

--------------------------------

### Offline 2D BIT Implementation in C++

Source: https://usaco.guide/plat/2DRQ_lang=cpp

An implementation of an offline 2D Fenwick Tree (BIT) in C++. This version is noted to be significantly slower than optimized versions due to a high constant factor but may be easier to understand. It requires standard C++ libraries like vector and algorithm. Indices are zero-indexed.

```cpp
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;


/**
 * Offline 2D Fenwick Tree implementation.
 * Note that all the update and query indices
 * are zero-indexed, and that the rows are not

```

--------------------------------

### Sqrt Structure for Blocking Queries - C++

Source: https://usaco.guide/plat/sqrt_lang=cpp

Implements a Sqrt structure to manage blocking for array elements. It precomputes sums for blocks of size sqrt(N) to optimize range sum queries and updates. The constructor initializes the blocks based on the input array.

```cpp
#include <bits/stdc++.h>
using namespace std;


struct Sqrt {
	int block_size;
	vector<int> nums;
	vector<long long> blocks;
	Sqrt(int sqrtn, vector<int> &arr) : block_size(sqrtn), blocks(sqrtn, 0) {
		nums = arr;
		for (int i = 0; i < nums.size(); i++) { blocks[i / block_size] += nums[i]; }


```

--------------------------------

### Lazy Segment Tree C++ Template

Source: https://usaco.guide/plat/RURQ_lang=cpp

A C++ template for a generic lazy segment tree supporting range updates and queries. It includes private members for tree size, the main tree, and a lazy propagation array. This provides a foundational structure for implementing various lazy segment tree operations.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<T> tree;
	vector<T> lazy;



```

--------------------------------

### BIT Code (from PURS module)

Source: https://usaco.guide/plat/RURQ

This C++ code snippet demonstrates the implementation of a Binary Indexed Tree (BIT) that supports range updates and range sum queries. It's designed for problems like those found in competitive programming, often seen in modules related to Point Update Range Sum (PURS).

```C++
#include <bits/stdc++.h>
using namespace std;


int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n, q;


```

--------------------------------

### Precompute Mobius Function - C++

Source: https://usaco.guide/plat/PIE

This C++ code snippet demonstrates how to precompute the Mobius function using a modified sieve. It initializes the mobius array and iterates through potential prime factors to calculate the mobius values. The time complexity is approximately O(V log V), where V is the maximum value.

```cpp
mobius[1] = -1;
for (int i = 1; i < VALMAX; i++) {
	if (mobius[i]) {
		mobius[i] = -mobius[i];
		for (int j = 2 * i; j < VALMAX; j += i) { mobius[j] += mobius[i]; }
	}
}
```

--------------------------------

### C++ Inclusion-Exclusion for String Pattern Matching

Source: https://usaco.guide/plat/PIE

Implements a solution using the inclusion-exclusion principle to count strings matching a specific subset of patterns. It calculates the number of strings matching at least a set of patterns and applies the principle over subsets. The time complexity is O((N choose k) * 2^(N-k) * M * N).

```cpp
const int MOD = 1000003;


int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	int ans = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		// subsets with exactly k patterns matters
		if (__builtin_popcount(mask) != k) { continue; }
		// iterate over all superset of current subset mask


```

--------------------------------

### Segment Tree for Springboards DP Optimization

Source: https://usaco.guide/plat/range-sweep

A C++ implementation of a segment tree designed to optimize the dynamic programming solution for the Springboards problem. This snippet is part of the PURS module and utilizes coordinate compression due to large input sizes. It requires standard C++ libraries and a Point struct definition.

```cpp
#include <bits/stdc++.h>
using namespace std;


struct Point {
	int x, y;
	int i;
	bool is_start;




```

--------------------------------

### Triangle Counting with Bitsets in C++

Source: https://usaco.guide/plat/bitsets_lang=cpp

Implements an efficient solution for counting trees within triangular lots using bitsets. It precomputes the orientation of each point relative to every directed edge and then uses bitwise AND operations on these bitsets to determine if a point lies within a triangle. The time complexity is improved significantly compared to a naive approach.

```C++
bitset<300> b[300][300];


int main() {
	input();
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			if (j != i)
				for (int k = 0; k < N; ++k)
					if (cross(v[i], v[j], v[k]) > 0) b[i][j][k] = 1;
	vector<int> res(N - 2);

```

--------------------------------

### Naive Set Merging in C++

Source: https://usaco.guide/plat/merging_lang=cpp

This code snippet demonstrates a naive approach to merging two sets in C++. It iterates through the smaller set and inserts each element into the larger set. The time complexity for merging two sets of sizes n and m is O(m log(n+m)), leading to a worst-case O(N^2 log N) for N elements.

```cpp
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int main() {
    std::set<int> a = {1, 3, 5};
    std::set<int> b = {2, 4, 6};
    
    // Naive merge: insert elements from b into a
    for (int x : b) {
        a.insert(x);
    }
    
    // Output the merged set
    std::cout << "Merged set: ";
    for (int x : a) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
    
    return 0;
}
```

--------------------------------

### Optimized DP with Prefix Sums - C++

Source: https://usaco.guide/plat/sqrt

This C++ code snippet shows an optimization for dynamic programming using prefix sums. It calculates DP values and updates prefix sums based on the current index modulo a divisor. This approach is useful for combining different algorithmic strategies to improve time complexity.

```cpp
for (int i = n - 1; i >= 0; i--) {
	dp[i] += s[a[i]][i % a[i]];
	dp[i] %= MOD;


	for (int j = 1; j <= x; j++) {
		s[j][i % j] += dp[i];
		s[j][i % j] %= MOD;
	}
}
```

--------------------------------

### Closest Pair of Points: Divide and Conquer (C++)

Source: https://usaco.guide/plat/sweep-line_lang=cpp

Implements a divide and conquer algorithm to find the closest pair of points. It sorts points by x-coordinate, recursively finds the closest pairs in halves, and then checks points within a 'delta' strip around the median. Requires points to be sortable by x-coordinate.

```cpp
#include <bits/stdc++.h>
using namespace std;


struct Point {
	long double x, y;
	bool operator<(const Point &other) {
		if (x == other.x) { return y < other.y; }
		return x < other.x;
	}
};

```

--------------------------------

### Matrix Multiplication for Linear Recurrences - C++

Source: https://usaco.guide/plat/matrix-expo

Provides a generic matrix multiplication function for square matrices using vectors of vectors. This function is templated to work with different data types and includes an assertion to ensure matrices are compatible for multiplication. It calculates the product into a temporary matrix `c` before assigning it back to `a`.

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


const int MOD = 1e9;


template <typename T> void matmul(vector<vector<T>> &a, vector<vector<T>> b) {
	int n = a.size(), m = a[0].size(), p = b[0].size();
	assert(m == b.size());
	vector<vector<T>> c(n, vector<T>(p));

```

--------------------------------

### Dynamic Programming with Jumps - C++

Source: https://usaco.guide/plat/sqrt

This code snippet demonstrates a dynamic programming approach to solve problems involving jumps. It iterates backward through an array, calculating the number of ways to reach subsequent states based on jump lengths. This is often used in problems where combined algorithms can optimize complexity.

```cpp
vector<int> dp(n, 1);
for (int i = n - 1; i >= 0; i--) {
	for (int x = i + a[i]; x <= n; x += a[i]) { dp[i] = (dp[i] + dp[x]) % MOD; }
}
```

--------------------------------

### Restaurant Customers: Sweep Line Implementation in C++

Source: https://usaco.guide/plat/sweep-line

This C++ code implements the sweep line algorithm to solve the Restaurant Customers problem. It converts customer arrival and departure times into events, sorts them, and sweeps through them to find the maximum number of concurrent customers. The time complexity is O(N log N) due to sorting.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	cin >> n;


	vector<pair<int, int>> events;
	for (int i = 0; i < n; i++) {
		int arrival, departure;
	
```

--------------------------------

### Distance Queries in a Tree (C++)

Source: https://usaco.guide/plat/binary-jump

This C++ code snippet provides the implementation for calculating the distance between two nodes in a tree. It leverages the pre-computed depths of nodes and the LCA of the two nodes using the formula: depth[a] + depth[b] - 2 * depth[lca(a, b)]. The time complexity is O((N+Q)logN).

```cpp
#include <cmath>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::vector;


 Code Snippet: LCA Tree (Click to expand) 



```

--------------------------------

### Generic Lazy Segment Tree Implementation

Source: https://usaco.guide/plat/RURQ

A C++ template class for a generic lazy segment tree supporting range updates and queries. It utilizes two arrays, 'tree' for segment values and 'lazy' for pending updates. This implementation requires careful handling of the push_down mechanism to ensure correct propagation of lazy updates.

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;


template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<T> tree;
	vector<T> lazy;


```

--------------------------------

### Subset Sum DP Implementation - C++

Source: https://usaco.guide/plat/dp-sos_lang=cpp

Implements the Subset Sum DP to calculate dp[x][i] which stores the sum of elements A[y] for all y in S(x,i). It iterates through all masks and bit positions, accumulating sums based on the bitwise XOR condition. The final SOS (Sum Over Subsets) for each mask is stored in the sos array.

```cpp
vector<int> sos(1 << n);
vector<vector<int>> dp(1 << n, vector<int>(n + 1));


for (int x = 0; x < (1 << n); x++) {
	dp[x][0] = a[x];
	for (int i = 0; i < n; i++) {
		dp[x][i + 1] = dp[x][i];
		if (x & (1 << i)) { dp[x][i + 1] += dp[x ^ (1 << i)][i]; }
	}
	sos[x] = dp[x][n];
}
```

--------------------------------

### C++ Centroid Decomposition Setup - Xenia & Tree

Source: https://usaco.guide/plat/centroid

This C++ code sets up the necessary data structures for centroid decomposition. It includes adjacency list, subtree size calculation, and a vector to store minimum distances to red nodes. INF is defined as a large value to represent infinity.

```cpp
#include <bits/stdc++.h>
using namespace std;


// a number that is large enough while not causing overflow
const int INF = 1e9;


vector<vector<int>> adj;
vector<int> subtree_size;
// min_dist[v] := the minimal distance between v and a red node
vector<int> min_dist;

```

--------------------------------

### C++ DP for String Pattern Matching with Bitmasking

Source: https://usaco.guide/plat/PIE

Implements a dynamic programming approach using bitmasking to count strings of a certain length that match a given set of patterns. The DP state dp[i][mask] represents the number of strings of length i matching patterns indicated by the mask. The time complexity is O(M*N*2^N).

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	ifstream in("cowpatibility.in");
	int n;
	in >> n;


	map<vector<int>, int> subsets;
	for (int i = 1; i <= n; i++) {


```

```cpp
const int MOD = 1000003;


int howMany(vector<string> patterns, int k) {
	int n = patterns.size();
	int m = patterns[0].size();
	vector<vector<int>> dp(50, vector<int>(1 << n));
	for (int i = 0; i < m; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			int mask = 0;
			for (int j = 0; j < n; j++) {


```

--------------------------------

### Naive DP for Leaf Color Problem

Source: https://usaco.guide/plat/VT_lang=cpp

This C++ code implements a naive O(n^2) dynamic programming solution for the 'Leaf Color' problem. It calculates the number of induced subgraphs that are trees rooted at a node 'v' where all leaves have a specific color 'c'. The transitions involve combining results from children and handling the root's color.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


constexpr int MAX_N = 2e5 + 1;
constexpr int MOD = 998244353;


int n, a[MAX_N];
ll dp[MAX_N], ans;

```

--------------------------------

### Leaf Color Naive DP Solution - C++

Source: https://usaco.guide/plat/VT

This C++ code implements a naive dynamic programming approach to solve the Leaf Color problem. It calculates the number of induced subgraphs that are trees rooted at a node 'v' where all leaves have a specific color 'c'. The solution iterates through all possible roots and colors, resulting in an O(n^2) time complexity.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


constexpr int MAX_N = 2e5 + 1;
constexpr int MOD = 998244353;


int n, a[MAX_N];ll dp[MAX_N], ans;

```

--------------------------------

### Divide and Conquer DP: C++ Implementation Snippet

Source: https://usaco.guide/plat/DC-DP

This C++ code snippet sets up basic constants and a 2D vector for calculations related to the Divide and Conquer DP optimization. It initializes a 'calc' table to store precomputed costs, likely for a problem involving distances or steps, and uses 'MAX_N' and 'MAX_K' for array dimensions. This is a foundational part for implementing the DP optimization.

```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long


const int MAX_N = 1000;
const int MAX_K = 7;


// calc[i][j] stores the # of steps to get all cows distance j away to door i
// to make implementing a cyclic array easier, we double the size
vector<vector<ll>> calc(2 * MAX_N, vector<ll>(MAX_N + 1, 0));

```

--------------------------------

### Polygon Area Calculation (C++)

Source: https://usaco.guide/plat/geo-pri_lang=cpp

Calculates the area of a polygon using the Shoelace formula. The time complexity is O(N), where N is the number of vertices in the polygon. Requires a vector of Point objects.

```cpp
#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	cin >> n;
	vector<Point> points(n);
	for (auto &p : points) { cin >> p; }


```

--------------------------------

### Cowpatibility Adjacency Bitset Initialization

Source: https://usaco.guide/plat/bitsets_lang=cpp

This code initializes adjacency bitsets for cow compatibility. It uses `std::bitset` to represent shared flavors between cows. The approach optimizes memory by only storing adjacency bitsets for the first half of the cows and then processing the second half. The `adj[x][y] = 1` indicates cow `x` and cow `y` share a flavor.

```cpp
#include <bits/stdc++.h>
using namespace std;


typedef long long ll;
typedef bitset<50000> B;
const int HALF = 25000;


int N;
B adj[HALF];
vector<int> flav[1000001];
```

--------------------------------

### Point Location Test (C++)

Source: https://usaco.guide/plat/geo-pri_lang=cpp

Checks the location of a point relative to a line segment using a cross-product-based formula. Returns 0 if collinear, positive if above, and negative if below. Time complexity is O(1).

```cpp
#include <bits/stdc++.h>
using namespace std;


long long collinear(Point p, Point p1, Point p2) {
	return 1LL * (p.y - p1.y) * (p2.x - p1.x) - 1LL * (p.x - p1.x) * (p2.y - p1.y);
}


int main() {


```

--------------------------------

### LCA Tree Implementation (C++)

Source: https://usaco.guide/plat/binary-jump

This C++ code snippet outlines the basic structure for a 'Tree' class, likely intended for Lowest Common Ancestor (LCA) calculations using binary lifting. It includes necessary headers and sets up a private member for the tree's internal representation, with a time complexity of O((N+Q)logN) for operations.

```cpp
#include <cmath>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;


class Tree {
  private:

```

--------------------------------

### Segment Intersection Test (C++)

Source: https://usaco.guide/plat/geo-pri_lang=cpp

Determines if two line segments intersect. It first checks for rectangle intersection and then verifies if segment endpoints lie on opposite sides of the other segment. The provided code snippet is incomplete.

```cpp
#include <bits/stdc++.h>
using namespace std;


int sign(long long num) {
	if (num < 0) {
		return -1;
	} else if (num == 0) {
		return 0;
	}

```

--------------------------------

### Matrix Multiplication for Fibonacci - C++

Source: https://usaco.guide/plat/matrix-expo

Implements matrix multiplication for 2x2 matrices, a core component for calculating Fibonacci numbers using matrix exponentiation. It uses `long long` for values and a constant for modulo operations. Assumes matrices are 2x2.

```cpp
#include <bits/stdc++.h>
using namespace std;


using ll = long long;


const ll MOD = 1e9 + 7;


using Matrix = array<array<ll, 2>, 2>;


Matrix mul(Matrix a, Matrix b) {

```

--------------------------------

### Segment Intersection: Sign Function (C++)

Source: https://usaco.guide/plat/geo-pri

Determines the sign of a long long integer. Returns -1 for negative, 0 for zero, and 1 for positive. This is a helper function for segment intersection tests, often used with cross products.

```cpp
#include <bits/stdc++.h>
using namespace std;

int sign(long long num) {
    if (num < 0) {
        return -1;
    } else if (num == 0) {
        return 0;
    } else {
        return 1;
    }
}
```
Tokens:
Raw