🚀 Competitive Programming in Java

⭐ If this repository helped you even a little, consider giving it a star!

---

This repository contains essential data structures and algorithms implemented in Java for competitive programming.

🔗 I'm SumitXorY / sumit_chauhan on coding platforms:
📘 Codeforces | 🍛 CodeChef

Feel free to use the codes — and if you find any bugs, don’t hesitate to report them!

---

📂 Contents

🧱 Data Structures

• Next Smaller & Bigger Element using Stack (O(n))
• Disjoint Set (Union-Find)
• Centroid Decomposition
• Lowest Common Ancestor (LCA)
• Virtual Tree
• Fenwick Tree / Binary Indexed Tree (BIT)
• Segment Tree - Basic
• Segment Tree - Range Updates (Add)
• Segment Tree - Range Updates (Assign)
• Kth Order Statistic on Subarray (No Updates)

📌 Algorithms

• Abstract Binary Search
• Breadth-First Search (BFS)
• Depth-First Search (DFS)
• Kruskal's Algorithm using DSU
• Dijkstra's Algorithm using PriorityQueue
• Floyd-Warshall (All-Pairs Shortest Path)
• LIS (Longest Increasing Subsequence) - O(n log n)
• PIE (Principle of Inclusion-Exclusion)

🧵 Strings

• String Hashing - Rolling Polynomial Hash

🧮 Math

• Sieve of Eratosthenes (n ≤ 10⁷)
• Fraction Handling
• Rounding Doubles
• Geometry: Segments, Intersections, Polygon Area
• Closest Pair of Points
• nCr with Modulo
• Next Permutation
• Selecting r Things from n Things
• Modular Power Function
• Matrix Exponentiation

---

🧪 Miscellaneous

• Java Template for Competitive Programming

---

⚡ Fast I/O for Java: Template

Inspired by uwi, this I/O template greatly improves Java input/output speed for contests.

🔧 Highlights

• Avoids slow Scanner and BufferedReader.
• No more TLE due to I/O after switching to this.
• Write your logic inside solve() — main() calls it.

---

📘 Template Documentation

🔹 Input Methods

int x = ni();             // next int
long y = nl();            // next long
double d = nd();          // next double
String s = ns();          // next string
char c = nc();            // next char
int[] arr = na(n);        // array of size n
char[][] grid = nm(n, m); // character matrix

🔹 Output Methods

pn(obj); // println
p(obj);  // print

🔹 Utilities

int maxVal = max(arr);   // max from array
int minVal = min(arr);   // min from array
int g = gcd(x, y);       // gcd of two numbers

Includes a custom Pair class supporting hashing and sorting — usable in HashSets, HashMaps, and TreeMaps.