一、二分算法
二分算法，堪称算法世界中的高效查找利器，其核心思想在于利用数据的有序性，通过不断将查找区间减半，快速定位目标元素或满足特定条件的位置。
1. 普通二分
普通二分适用于在有序数组中查找特定元素的位置。我们可以进一步细分需求，如查找满足条件的最左边的数的下标，或者最右边的数的下标。以代码中的 find1 和 find2 函数为例：
cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n, m;
int find1(int x) {
int l = 0, r = n + 1;
int ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] > x) {
r = mid - 1;
}
else if (a[mid] == x) {
ans = mid;
r = mid - 1;
}
else if (a[mid] < x) {
l = mid + 1;
}
}
return ans;
}
int find2(int x) {
int l = 0, r = n + 1;
int ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (a[mid] > x) {
r = mid - 1;
}
else if (a[mid] == x) {
ans = mid;
l = mid + 1;
}
else if (a[mid] < x) {
l = mid + 1;
}
}
return ans;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (m--) {
int tmp;
cin >> tmp;
cout << find1(tmp) - 1 << ' ' << find2(tmp) - 1 << endl;
}
return 0;
}
在 find1 函数中，当找到与 x 相等的元素时，我们继续将右边界 r 调整为 mid - 1，目的是持续向左查找，确保最终得到的是最左边的符合条件的下标。而 find2 函数在找到相等元素后，将左边界 l 调整为 mid + 1，以此向右查找最右边的符合条件的下标。这种技巧在处理重复元素较多的数组时，能够精准定位特定位置，为后续的数据处理提供极大便利。
2. 数值二分
数值二分则是将二分思想应用于数值求解领域。例如，在求一个浮点数的三次方根问题中，我们利用数值二分的方法可以高效且准确地得到结果。
cpp
#include<iostream>
#include<iomanip>
using namespace std;
double n, l, r, mid;
double q(double a) {
return a * a * a;
}
int main() {
cin >> n;
l = -10000, r = 10000;
while (r - l >= 1e-7) {
mid = (l + r) / 2;
if (q(mid) >= n) r = mid;
else l = mid;
}
cout << fixed << setprecision(6) << l;
return 0;
}
我们先确定一个可能包含三次方根的区间 [l, r]，在这个例子中，由于任何实数的三次方根都在 -10000 到 10000 这个较大范围之内（对于一般竞赛和实际应用场景中的数值而言），我们以此作为初始区间。然后，通过不断缩小区间范围，当区间长度小于一定精度（这里是 1e-7）时，我们认为此时的左边界 l 就是所求三次方根的近似值。数值二分在处理这类数值逼近问题时，展现出了极高的效率和稳定性，相较于暴力枚举等方法，大大减少了计算量。
二、排序算法
排序算法是数据处理领域的核心算法之一，它能够将无序的数据整理成有序的序列，为后续的数据查找、统计、分析等操作奠定基础。
1. 快速排序
快速排序凭借其高效的性能，在众多排序算法中脱颖而出，广泛应用于各类场景。它基于分治策略，通过选择一个基准值，将数组划分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值，然后递归地对左右两部分进行排序。
cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int n;
void q(int l, int r) {
if (l >= r) return;
if (l + 1 == r) {
if (a[l] > a[r]) swap(a[l], a[r]);
return;
}
int i = l - 1, j = r + 1;
int x = a[(i + j) >> 1];
while (i <= j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
q(l, j); q(j + 1, r); // 注意这里是j
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
q(0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
}
在代码中，我们选取数组中间位置的元素作为基准值 x。通过两个指针 i 和 j 从数组两端向中间移动，将小于基准值的元素交换到左边，大于基准值的元素交换到右边。当 i 和 j 相遇时，数组就被划分成了符合条件的两部分。随后，递归地对这两部分继续进行快速排序，直至整个数组有序。快速排序的平均时间复杂度为 O(nlogn)，在数据量较大时表现出色。
快排的延展：第 k 个数
基于快速排序的思想，我们可以进一步拓展其应用，快速找出数组中第 k 小的数。这在很多需要统计特定位置元素的场景中非常实用。
cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int n;
int q(int l, int r, int k) {
if (l >= r) return a[l];
if (l + 1 == r) {
if (a[l] > a[r]) swap(a[l], a[r]);
if (k == 1) return a[l];
return a[r];
}
int i = l - 1, j = r + 1;
int x = a[(i + j) >> 1];
while (i <= j) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
}
int len = j - l + 1;
if (k <= len) // 注意这里的是k<=len,而不是k<=j+1
return q(l, j, k);
return q(j + 1, r, k - len);
}
int main() {
int k;
cin >> n >> k;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
cout << q(0, n - 1, k);
}
在每次划分后，我们计算左半部分的长度 len。如果 k 小于等于 len，说明第 k 小的数在左半部分，我们递归在左半部分查找；否则，在右半部分查找，并且将 k 调整为 k - len，因为我们已经排除了左半部分的 len 个数。这种方法避免了对整个数组进行完全排序，大大提高了查找特定位置元素的效率。
2. 归并排序
归并排序同样是一种基于分治思想的排序算法，它将数组逐步分解为较小的子数组，分别进行排序后，再将这些有序的子数组合并成一个最终的有序数组。
cpp
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int a[N];
int tmp[N];
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(l, mid); merge_sort(mid + 1, r);
int ls = l, rs = mid + 1; int tmpread = 0;
while (ls <= mid && rs <= r) {
if (a[ls] < a[rs]) tmp[tmpread++] = a[ls++];
else tmp[tmpread++] = a[rs++];
}
while (ls <= mid) tmp[tmpread++] = a[ls++];
while (rs <= r) tmp[tmpread++] = a[rs++];
for (int i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
merge_sort(0, n - 1);
for (int i = 0; i < n; i++) cout << a[i] << ' ';
return 0;
}
在代码实现中，我们首先将数组递归地划分为左右两部分，直到子数组长度为 1（此时子数组自然有序）。然后，在合并阶段，通过两个指针 ls 和 rs 分别指向左右两个子数组的起始位置，比较并将较小的元素依次放入临时数组 tmp 中。当其中一个子数组遍历完后，将另一个子数组剩余的元素直接复制到 tmp 中。最后，将 tmp 数组中的元素复制回原数组 a，完成一次合并。归并排序的时间复杂度稳定在 O(nlogn)，并且它是一种稳定的排序算法，即在排序过程中，相同元素的相对顺序保持不变。
归并排序的延伸：逆序对
归并排序的思想还可以巧妙地用于统计数组中的逆序对数量。逆序对在许多算法问题中有着重要的应用，比如计算数组的无序程度等。
cpp
#include <iostream>
using namespace std;
const long long N = 1000010;
long long n;
long long a[N];
long long tmp[N];
// 归并排序并统计逆序对数量
long long merge_sort(long long l, long long r) {
if (l >= r) return 0;
if (l + 1 == r) {
if (a[l] > a[r]) {
swap(a[l], a[r]);
return 1;
}
return 0;
}
long long mid = l + r >> 1;
long long res = merge_sort(l, mid) + merge_sort(mid + 1, r);
long long ls = l, rs = mid + 1, tmpread = 0;
while (ls <= mid && rs <= r) {
if (a[ls] <= a[rs]) {
tmp[tmpread++] = a[ls++];
}
else {
// 当 a[ls] > a[rs] 时，a[ls...mid] 都与 a[rs] 构成逆序对
res += mid - ls + 1;
tmp[tmpread++] = a[rs++];
}
}
while (ls <= mid) tmp[tmpread++] = a[ls++];
while (rs <= r) tmp[tmpread++] = a[rs++];
for (long long i = l, j = 0; i <= r; j++, i++) a[i] = tmp[j];
return res;
}
int main() {
cin >> n;
for (long long i = 0; i < n; i++) cin >> a[i];
cout << merge_sort(0, n - 1);
return 0;
}
在合并过程中，当我们发现 a[ls] > a[rs] 时，这意味着 a[ls] 到 a[mid] 这 mid - ls + 1 个元素都与 a[rs] 构成逆序对，因此将这个数量累加到结果 res 中。通过递归地进行归并排序和逆序对统计，我们能够高效地得到整个数组的逆序对数量。
三、区间和
在处理区间和相关问题时，离散化与树状数组的组合是一种非常强大的解决方案。当我们面对无限长数轴上的区间操作，或者数据范围过大导致直接存储和处理困难时，离散化可以将实际用到的数据映射到一个较小的连续空间中，大大减少内存占用和计算量。而树状数组则为快速更新和查询区间和提供了便利。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 树状数组类
class FenwickTree {
private:
vector<int> tree;
int n;
// 计算最低位的 1 所代表的值
int lowbit(int x) {
return x & -x;
}
public:
FenwickTree(int size) : n(size), tree(size + 1, 0) {}
// 单点更新操作
void update(int idx, int val) {
while (idx <= n) {
tree[idx] += val;
idx += lowbit(idx);
}
}
// 前缀和查询操作
int query(int idx) {
int res = 0;
while (idx > 0) {
res += tree[idx];
idx -= lowbit(idx);
}
return res;
}
};
// 二分查找数值对应的下标
int find(int x, const vector<int>& a) {
int l = 0, r = a.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
// 如果 x 小于最小的位置，返回 0
if (a[l] > x) return 0;
return l + 1; // 下标从 1 开始
}
int main() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> operations(n);
vector<pair<int, int>> queries(m);
vector<int> all_positions;
// 读取操作并记录所有位置
for (int i = 0; i < n; ++i) {
cin >> operations[i].first >> operations[i].second;
all_positions.push_back(operations[i].first);
}
// 读取查询并记录所有位置
for (int i = 0; i < m; ++i) {
cin >> queries[i].first >> queries[i].second;
all_positions.push_back(queries[i].first);
all_positions.push_back(queries[i].second);
}
// 离散化处理
sort(all_positions.begin(), all_positions.end());
all_positions.erase(unique(all_positions.begin(), all_positions.end()), all_positions.end());
// 创建树状数组
FenwickTree fenwickTree(all_positions.size());
// 执行操作
for (const auto& op : operations) {
int idx = find(op.first, all_positions);
fenwickTree.update(idx, op.second);
}
// 处理查询
for (const auto& query : queries) {
int l = find(query.first, all_positions);
int r = find(query.second, all_positions);
int result = fenwickTree.query(r) - fenwickTree.query(l - 1);
cout << result << endl;
}
return 0;
}