### 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;

```

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

### 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...);

```

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

### 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;


```

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

### 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;
	}
}


```

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

### 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;


```

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

### 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
```

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

### 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]; }
}
```

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

### 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;
}
```

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

### 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


```

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

### 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";
}
```

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

### 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++) {

}
```

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

### 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";
}
```

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

### 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) {


```

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

### 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;

```

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

### 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();

}
```

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

### 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() {


```

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

### 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() {

```

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

### 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:

```

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

### 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 {

```

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

### 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();
}
```

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

### 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;


```

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

### 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;
	}

```

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

### 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;
	}
```

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

### 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];
```

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

### 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;

```

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

### 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) {

```

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

### Path Queries II Implementation - C++

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

This C++ code snippet is part of an implementation for 'Path Queries II', likely using Heavy-Light Decomposition and a Segment Tree. It sets up the main function for competitive programming, optimizing I/O operations. The code indicates the use of HLD and Segment Tree data structures for tree-based queries.

```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);

```

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

### 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;
    }
}
```

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

### SOS DP Implementation for Vowel Disjointness

Source: https://usaco.guide/plat/dp-sos

This C++ code snippet sets up the structure for solving a problem involving vowel disjointness using SOS DP. It includes necessary headers, defines a constant for the maximum number of bits, and declares an array to store the SOS DP states. The main function reads input and begins the process.

```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++) {

```

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

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

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

This C++ code implements an offline approach to answer range queries on a static array using the divide and conquer paradigm. It preprocesses the array to efficiently answer queries involving associative operations. The function `divi` recursively divides the array and queries, calculating prefix and suffix aggregates. Dependencies include standard C++ libraries and a `vi` type (likely std::vector).

```cpp
int n, q, A[MX], B[MX];
vi x, ans;
int lef[MX], rig[MX];


void divi(int l, int r, vi v) {
	if (!sz(v)) return;
	if (l == r) {
		trav(_, v) ans[_] = x[l];
		return;
	}


```