Core Logic and Mathematical Principles
Merge Sort for Counting Inversions
An inversion is defined as a pair $(i, j)$ satisfying $i < j$ and $A[i] > A[j]$. The brute-force solution has $O(N^2)$ complexity.
In merge sort, based on the divide-and-conquer paradigm, the sequence $A[l..r]$ is divided into $A[l..mid]$ and $A[mid+1..r]$. During the two-pointer linear scanning phase of the merge operation, if $A[p_2] < A[p_1]$ is satisfied, since the left subsequence is guaranteed to be sorted in ascending order, all remaining elements in $A[p_1..mid]$ are strictly greater than $A[p_2]$. At this point, the number of cross-inversion pairs is added in a single batch with the contribution value:
$$\Delta = mid - p_1 + 1$$
The total time complexity is $O(N \log N)$, and the space complexity is $O(N)$.
Bitwise Fast Exponentiation
Compute $a^b \pmod m$. If using linear iteration, the complexity is $O(b)$. Based on binary decomposition, $b$ can be uniquely represented as:
$$b = \sum_{i=0}^{k} c_i \cdot 2^i \quad (c_i \in \{0, 1\})$$
According to the laws of exponents:
$$a^b = \prod_{i=0}^{k} a^{c_i \cdot 2^i}$$
Using the doubling technique, at each iteration, let the base $a \leftarrow a^2 \pmod m$. If the current lowest bit of the exponent satisfies $b \& 1 = 1$, multiply the current base $a$ into the global answer and take the modulo. Shift the exponent $b$ right by one bit ($b \leftarrow b \gg 1$) to examine the next bit. The time complexity is reduced to $O(\log b)$, and the space complexity is $O(1)$.
Recursion (decrease-and-conquer) is about breaking down problems; iteration (doubling) is about building answers.
Algorithm Derivation and State Design
Merge Sort for Counting Inversions Derivation
The divide-and-conquer process satisfies the recurrence:
$$ T(N) = 2T\left(\frac{N}{2}\right) + O(N) $$
Solving yields $T(N) = O(N \log N)$. During merging, set two pointers $i = l, j = mid + 1$.
- If $A[i] \le A[j]$: $A[i]$ is placed in order, no inversion is generated, $i \leftarrow i + 1$.
- If $A[i] > A[j]$: $A[j]$ is placed in order, meaning that $A[i]$ and all elements to its right up to $mid$ form inversions with $A[j]$. The counter $ans \leftarrow ans + (mid - i + 1)$, $j \leftarrow j + 1$.
Bitwise Fast Exponentiation Derivation
Let $ans = 1 \pmod m$. The loop condition is $b > 0$:
- Check the lowest bit:
if (b & 1)$\Rightarrow$ $ans = ans \cdot a \pmod m$. - The base squares itself: $a = a \cdot a \pmod m$.
- Shift the exponent right by one bit:
b >>= 1.
Templates
Merge Sort for Counting Inversions
// long long to avoid overflow
long long cnt = 0;
void merge_sort(vector<int>& a, vector<int>& temp, int l, int r) {
if (l >= r) return;
int mid = l + ((r - l) >> 1); // Bitwise operation replaces division, prevents overflow and speeds up
// 1. Divide and conquer: recursively split the problem
merge_sort(a, temp, l, mid);
merge_sort(a, temp, mid + 1, r);
// 2. Merge: two-pointer linear scan
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
// All remaining elements in the left subsequence form inversions with a[j], batch accumulate
cnt += (mid - i + 1);
}
}
// 3. Cleanup and array copy back
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (i = l; i <= r; ++i) a[i] = temp[i];
}
Bitwise Fast Exponentiation
long long quick_pow(long long a, long long b, long long m) {
long long ans = 1 % m; // When m=1, any number modulo m must return 0
a %= m; // Prevent initial base a >= m from causing overflow in subsequent multiplication
while (b > 0) {
if (b & 1) {
// Current bit is valid, multiply into the answer
ans = ans * a % m;
}
a = a * a % m; // Base doubles
b >>= 1; // Exponent shifts right, halving the scale
}
return ans;
}
NOIP Practical Pitfall Guide
Inversion Counter Overflow in int
- In the extreme case, a strictly decreasing sequence of length $N$ contains $\frac{N(N-1)}{2}$ inversions. At the common NOIP data range $N = 5 \times 10^5$, the maximum number of inversions is approximately $1.25 \times 10^{11}$, far exceeding the $2 \times 10^9$ upper limit of
int. The counter must be declared aslong long; otherwise, integer overflow will turn it into a negative value.
Fast Exponentiation Multiplication Overflow and the $m=1$ Edge Case
- Multiplication overflow boundary: Without using
__int128, the ordinarya * a % moperation can only safely handle data ranges where $m \le 3 \times 10^9$ (such as the common $10^9+7$). If the problem provides a modulus $m$ reaching the $10^{18}$ level, the direct multiplication of twolong longvalues will overflow 64-bit integers. In such cases, an $O(\log m)$ "fast multiplication" (also known as "Russian peasant multiplication") algorithm must be used for split-modulo multiplication. - $m=1$ edge case blind spot: When the modulus $m=1$ appears in test data, by the definition of modular arithmetic, the result of any number modulo $1$ must be $0$. If the code blindly initializes the answer as
ans = 1, all test cases with $m=1$ will be judged incorrectly. Therefore, the answer initialization must be written asans = 1 % m.
Classic NOIP/Luogu Problems
Luogu P1908 Inversions
- Problem Description: Given a sequence of length $N$, find the total number of inversions. $N \le 5 \times 10^5$, and the elements satisfy $A[i] \le 10^9$.
- Problem Essence and Core Solution: The purest inversion counting template problem. Since $N \le 5 \times 10^5$, $O(N^2)$ brute-force enumeration is infeasible. Although the element size $A[i] \le 10^9$ is large, merge sort only depends on the relative ordering of elements, naturally immune to large numerical values, and does not require the cumbersome discretization preprocessing needed by Fenwick tree solutions. During the two-pointer linear merge, the ascending property of the left subsequence is used to batch-accumulate contributions, achieving $O(N \log N)$ time complexity.
Core Code
long long cnt = 0; // Global counter, preventing answer overflow for extreme strictly decreasing sequences
void merge_sort(vector<int>& a, vector<int>& temp, int l, int r) {
if (l >= r) return;
int mid = l + ((r - l) >> 1);
merge_sort(a, temp, l, mid);
merge_sort(a, temp, mid + 1, r);
int i = l, j = mid + 1, k = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
// Core: since the left subsequence is ascending, if a[i] > a[j],
// then all elements from i to mid form inversions with a[j]
cnt += (mid - i + 1);
}
}
while (i <= mid) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (i = l; i <= r; ++i) a[i] = temp[i];
}
Luogu P1226 [Template] Fast Exponentiation
- Problem Description: Given three integers $a, b, p$, find the value of $a^b \pmod p$. $a, b, p \le 2 \times 10^9$.
- Problem Essence and Core Solution: Tests modular exponentiation optimization under large exponents. The core idea is to decompose the exponent $b$ into binary bits (decrease-and-conquer), reducing the original problem to $O(\log b)$ multiplications. According to the data range, the modulus $p \le 2 \times 10^9$, so the maximum intermediate multiplication result is approximately $(2 \times 10^9)^2 = 4 \times 10^{18}$, which is within the safe upper limit of standard
long long(approximately $9 \times 10^{18}$). Additionally, special attention must be paid to thep = 1boundary case.
Core Code
long long quick_pow(long long a, long long b, long long p) {
long long ans = 1 % p; // Pitfall prevention: if p=1, the result of any number modulo p must be 0
a %= p; // Pitfall prevention: avoid initial a >= p causing overflow in the first multiplication
while (b > 0) {
if (b & 1) {
ans = ans * a % p; // As long as p <= 2*10^9, long long multiplication has no overflow risk
}
a = a * a % p; // Base doubles
b >>= 1; // Exponent shifts right, problem scale halves
}
return ans;
}