int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i++; while (q[i] < x); do j--; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j); quick_sort(q, j + 1, r);
}
<br> ## Merge Sort <br> 1. Determine demarcation point (midpoint) 2. Recursively sort left and right segments 3. Merge left and right segments <br> ```c++ int tmp[MN]; void merge_sort(int q[], int l, int r) { if (l >= r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid + 1, r); int idx = 0, i = l, j = mid + 1; while (i <= mid && j <= r) { if (q[i] <= q[j]) tmp[idx++] = q[i++]; else tmp[idx++] = q[j++]; } while (i <= mid) tmp[idx++] = q[i++]; while (j <= r) tmp[idx++] = q[j++]; for (i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j]; }
// r = mid
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
// l = mid
int bsearch(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
<br> ## Binary Search for Rational Numbers <br> ```c++ const double eps = 1e-6; bool check(double x) {/* .. */} double bsearch(double l, double r) { while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; }
vector<int> C; int t = 0; for (int i = 0; i < A.size; ++i) { t += A[i]; if (i < B.size()) t += B[i]; C.push_back(t % 10); t /= 10; } if (t) C.push_back(t); return C;
}
<br> ## Large Integer Subtraction <br> 1. $C = A - B$ 2. $condition:A \geq B \geq 0$ <br> ```c++ vector<int> sub(vector<int> &A, vector<int> &B) { vector<int> C; int t = 0; for (int i = 0; i < A.size(); ++i) { t = A[i] - t; if (i < B.size()) t -= B[i]; C.push_back((t + 10) % 10); if (t < 0) t = 1; else t = 0; } while (C.size > 1 && C.back() == 0) C.pop_back(); return C; }
while (C.size > 1 && C.back() == 0) C.pop_back(); return C;
}
<br> ## Large Integer Divided by Small Integer <br> 1. $A/B=C\dots r$ 2. $condition:A\geq0,\ b>0$ <br> ```c++ vector<int> div(vector<int> &A, int b, int &r) { vector<int> C; r = 0; for (int i = A.size() - 1; ~i; --i) { r = r * 10 + A[i]; C.push_back(r / b); r %= b; } reverse(C.begin(), C.end()); while (C.size() > 1 && C.back() == 0) C.pop_back(); return C; }
\(a[l] + ... + a[r] = S[r] - S[l - 1]\)
sum of submatrix with \([x_1,y_1]\) as upper left coner and \([x_2, y_2]\) as lower right corner \(=\)
\(S[x_1 - 1, y_2] - S[x_2, y_1 - 1] + S[x_1 - 1, y_1 - 1]\)
B[l]\ += c, B[r + 1] -= c;
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c;
n >> k & 1;
lowbit(n) = n & -n;
int find(int x) // solve the discretized value corresponding to x
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r / 2;
if (alls[mid] >= x) r = mid; // find the first number >= x
else l = mid + 1;
}
return r + 1; // map to 1, 2, ..., n
}
<br> # Merge Intervals <br> ```c++ #define pair<int, int> PII; vector<PII> segs; // segments to be merged void merge(vector<PII> &segs) { vector<PII> res; sort(segs.begin(), segs.end()); int st = -2e9, end = -2e9; for (auto seg : segs) { if (ed < seg.first) { if (st != -2e9) res.push_back({st, ed}); st = seg.first, ed = seg.second; } else ed = max(ed, seg.second); } if (st != -2e9) res.push_back({st, ed}); // consider the last segment segs = res; }