模板

老祖宗传的板子

IO

optimize优化

二分 & 三分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//二分
int l, r, mid;
while (l < r) {
mid = (l + r /* + 1*/) >> 1; //手推一下 l + 1 == r 的情况,考虑是否加一
if (check(mid)) r = mid;
else l = mid + 1;
}

//精度二分
double l, r, mid, eps;
while (l + eps < r) {
mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + eps;
}

//三分求f最小值(最大值改一改)
//最优的三分不是均匀分成3块,而是在mid左右两侧取值,这样显然更快。
int l, r, mid;
while (r - l >= 3) {
mid = (l + r) >> 1;
if (f(mid) > f(mid + 1)) l = mid + 1;
else r = mid;
}
//为了避免边界错误,分到只剩3个数就枚举一遍。
int ans, tmp = INT_MAX;
for (int i = l; i <= r; i++) {
if (f(i) < tmp) {
ans = i;
tmp = f(i);
}
}

数据结构

单调栈 & 单调队列

单调栈一般维护当前节点往前找到的第一个小于/大于它的点,分别对应递增栈/递减栈。

1
2
3
4
5
6
7
8
//递增栈
stack<int> s;
for (int i = 1; i <= n; i++) {
while (!s.empty() && num[s.top()] >= num[i]) s.pop();
min_left[i] = s.top();
s.push(i);
}
//min_left中存储向左第一个小于它的节点的下标。

单调队列一般维护当前节点往前找m个点的最大/小值,分别对应递增队列/递减队列。一般用 deque 实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//递增队列
while (!q.empty()) q.pop_back();
num[0] = num[n + 1] = inf;
q.push_back(0);
for (int i = 1; i < k; i++) {
while (!q.empty() && num[q.back()] >= num[i]) q.pop_back();
q.push_back(i);
}
for (int i = k; i <= n; i++) {
while (!q.empty() && num[q.back()] >= num[i]) q.pop_back();
q.push_back(i);
while (!q.empty() && q.front() < i - k + 1) q.pop_front();
minium[i - k + 1] = num[q.front()];
}

树状数组

普通树状数组

二维树状数组

线段树

珂朵莉树

By CmsMartin

平衡树

红黑树

By CmsMartin

自顶向下Splay