Recommended Learning Blogs

1. Slope optimization: Covers both core implementation methods with accompanying example prolbems.
2. In-depth explanation of the static keyword in C++
3. Fast Fourier Transform (FFT) tutorials
4. Knuth-Morris-Pratt (KMP) string matching algorithm guides

Practical Coding Tips

1. Efficient Mass String Input Handling: Utilize stringstream for streamlined parsing of large volumes of string input data.

2. Handling Ultra-Large Integers Without Big Integer Libraries: When dealing with numbers exceeding the range of __int128 but avoiding arbitrary-precision code, long double is a viable alternative. It supports values from approximately \(1.2 \times 10^{-4932}\) to \(1.2 \times 10^{4932}\), which works for \(10^{1000}\) even with minor precision loss. Note that direct output may trigger scientific notation:

// Large integer value
long double largeInt = 12345678;
// Small decimal with few significant digits
long double smallDecimal = 0.00001234;

cout << largeInt << endl;
cout << smallDecimal << endl;

Output:

1.23457e+07
1.234e-05

To disable scientific notation and output as plain integers, use the fixed manipulator combined with setprecision(0) to suppress decimal places: cout << fixed << setprecision(0) << largeInt << endl;.

3. Structured Matrix Operations:

   • Encapsulate matrices in a struct for clean code organization:

   struct Mat {
       long long arr[5][5];
       void init() {
           // Zero-initialize the matrix
           memset(arr, 0, sizeof(arr));
       }
   };
   

   • Initialize transformation matrices to the identity matrix. For faster access, you can define a constant identity matrix:

   const Mat IDENTITY = {
       {{1,0,0,0,0},
        {0,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,0},
        {0,0,0,0,1}}
   };
   

   • Overload the multiplication operator for matrix multiplication (modulo a given value):

   Mat operator*(const Mat& lhs, const Mat& rhs, int mod) {
       Mat res;
       res.init();
       for (int i = 0; i < 5; ++i) {
           for (int k = 0; k < 5; ++k) {
               if (lhs.arr[i][k] == 0) continue; // Optimization
               for (int j = 0; j < 5; ++j) {
                   res.arr[i][j] = (res.arr[i][j] + 1LL * lhs.arr[i][k] * rhs.arr[k][j]) % mod;
               }
           }
       }
       return res;
   }
   

   (Note: Reordered loops for potential cache optimization while maintaining correctness.)

4. Tree Diameter Calculation: Use a two-pass DFS approach:

   1. Pick any node, perform DFS to find the farthest node st from it.
   2. Perform DFS again starting from st; the farthest node from st gives the end of the tree diameter. The distance between st and this node is the diameter length. To retrieve the diameter path, track parent pointers during DFS and backtrack from the farthest node:

   const int MAXN = 100005;
   vector<int> adj[MAXN];
   int depth[MAXN], parent[MAXN];
   
   void dfs(int u, int p) {
       parent[u] = p;
       depth[u] = depth[p] + 1;
       for (int v : adj[u]) {
           if (v == p) continue;
           dfs(v, u);
       }
   }
   
   int main() {
       // Build adjacency list...
       dfs(1, 0);
       int st = 1;
       for (int i = 1; i <= n; ++i) {
           if (depth[i] > depth[st]) st = i;
       }
       dfs(st, 0);
       int endNode = st;
       for (int i = 1; i <= n; ++i) {
           if (depth[i] > depth[endNode]) endNode = i;
       }
       // Output the diameter path
       vector<int> path;
       for (int cur = endNode; cur != 0; cur = parent[cur]) {
           path.push_back(cur);
       }
       reverse(path.begin(), path.end());
       for (int node : path) cout << node << " ";
   }
   

Common Pitfalls to Avoid

1. Uncleared Data Between Test Cases: Failing to reset arrays, variables, or data structures between test cases will lead to incorrect results. Always confirm the correct range to clear (e.g., 1 to n vs 0 to m).
2. Silent Overflow: Even if individual variables fit in int, their product (like n * m) may overflow. Cast to long long explicitly:

   // Incorrect: May overflow if n and m are large ints
   if (n * m > s) return;
   // Correct: Prevents overflow
   if (1LL * n * m > (long long)s) return;
   

3. Mo's Algorithm Loop Order: The four while loops adjusting the current window must maintain l <= r to avoid errors. The safe order is to expand the window first, then shrink it:

   while (current_l > query_l) add(--current_l);
   while (current_r < query_r) add(++current_r);
   while (current_l < query_l) del(current_l++);
   while (current_r > query_r) del(current_r--);
   

   (Here, add() updates the answer when including an element, del() updates when excluding it.)

Mo's Algorithm Sorting Notes

Pay close attention to the priority of comparison criteria: compare block IDs first, then adjust based on query endpoints (or time for time-travel Mo's). Ensure you reference struct members correctly to avoid logic errors. For example, this incorrect comparator:

bool cmp(Query a, Query b) {
    if (block_id[a.l] != block_id[b.l]) return block_id[a.l] < block_id[b.l];
    if (block_id[a.r] != block_id[a.r]) return block_id[a.r] < block_id[b.r]; // Typo: a.r instead of b.r
    return a.time < b.time;
}

Should be corrected to:

bool cmp(Query a, Query b) {
    if (block_id[a.l] != block_id[b.l]) return block_id[a.l] < block_id[b.l];
    if (block_id[a.r] != block_id[b.r]) return block_id[a.r] < block_id[b.r];
    return a.time < b.time;
}