【复习笔记】Week 1 数据结构
NCC79601
2019-10-22 23:16:34
# DAY 1
## 线段树
有些时候线段树维护的是 **贪心** 出来的东西，比如：维护$\frac {a[i]-a[j]}{i-j}$的最大值，支持单点修改。经过论证，此处的最大值只可能在$i-j=1$的情况下取得（画图可证），因此只用线段树维护差分序列即可。
[此题](https://ac.nowcoder.com/acm/problem/15949) 中线段树甚至可以用于实现 **类似平衡树** 的功能，具体为维护区间最大值，然后进行线段树上的分层二分查找。
## 树状数组
**二维** 树状数组的写法：
```cpp
void add(int x, int y, int v) {
for (int i = x; i <= n; i += i & (-i))
for (int j = y; j <= n; j += j & (-j))
c[i][j] += v;
return ;
}
int query(int x, int y) {
int res = 0;
for (int i = x; i; i -= i & (-i))
for (int j = y; j; j -= j & (-j))
res += c[i][j];
return res;
}
```
树状数组当然可以动态维护逆序对，对于逆序对问题可以先离散化（不能去重）然后再用权值树状数组。
还有一些情况，树状数组维护的信息是 **复杂的**。比如可以使用 **乘法分配律**，将一些信息合并，然后用树状数组统计，最后得到答案。
# DAY 2
## 堆
手写堆当然没什么用处。STL 可以帮助水完许多题目，因此有关堆的题目思维难度都很大。很多时候，题目需要用到 **贪心** 思想来建堆。
比如 [例题](https://ac.nowcoder.com/acm/problem/20154)： 有$n$个任务，每个任务有各自的用时$t_1$和完成期限$t_2$，如果到$t_2$还没完成，那么该任务作废。不能同时完成多个任务，必须完成一个任务以后才能完成下一个任务。现在需要求出最多能完成多少个任务。
这时就需要用到贪心思想。首先对所有任务按照 `dl` 进行升序排序，然后用一个堆来维护已选来完成的任务里最大的用时。维护一个当前时间 `now` 和当前答案 `ans`（单增），如果一个任务满足 `now + a[i].t <= a[i].dl`，可以直接完成这个任务，`ans++`，然后扔进堆里；否则，如果 `a[i].t` 小于 `q.top()`，既然堆里的任务都可以在 `now` 内完成，并且其 `dl` 一定比当前的任务更早，所以把 `q.top()` 那个任务换成当前任务也肯定能够完成，并且能够使 `now` 减小。因此，直接贪心地将堆顶换为当前任务的用时即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1.5e5 + 10;
struct node {
int t, dl;
bool operator < (const node &rhs) const {
return dl < rhs.dl;
}
} a[MAXN];
priority_queue<int> q;
// 堆顶保存已选的最大完成时间
int n, now = 0, ans = 0;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i].t, &a[i].dl);
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
// 核心贪心
if (now + a[i].t <= a[i].dl) {
now += a[i].t;
ans++;
q.push(a[i].t);
} else if (!q.empty() && a[i].t < q.top()) {
now += a[i].t - q.top();
q.pop();
q.push(a[i].t);
}
}
printf("%d", ans);
return 0;
}
```
另外，堆甚至可以用来维护一个区间内的前$k$大 / 小数的和。
比如 [例题](https://ac.nowcoder.com/acm/problem/17315)：选$m$个物品，要在满足放得进背包的前提下，让价值的中位数最大。
乍一看这题真的恶心，不过可以一步步分解这个问题。首先，$m$可以分奇偶性讨论。在这里就只考虑$m$为奇数的情况，设 `mid = m >> 1`，首先考虑把所有物品按照$v$为第一关键字，$w$为第二关键字进行升序排序，然后用两个数组 `pre[]` 和 `suf[]`，表示$[1,i)$和$(i,n]$内前 `mid` 小数的和。这样也是为了用 **贪心** 的思想来处理。这样统计完以后，就可以倒序枚举$[mid+1,n-mid]$区间内的物品，以当前物品为中位数，计算出最小代价即 `pre[i] + suf[i] + a[i].w`，第一次发现这个值小于$V$即找到了最大的中位数，最后输出即可。而当$m$为偶数的时候，需要考虑中位数是中间两数的平均数，所以 `pre[]` 和 `suf[]` 维护的是闭区间，在统计答案的时候稍作调整即可。
```cpp
// https://ac.nowcoder.com/acm/problem/17315
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
typedef long long ll;
struct node {
ll v, w;
bool operator < (const node &rhs) const {
if (v != rhs.v)
return v < rhs.v;
return w < rhs.w;
}
} a[MAXN];
int n, m;
ll v, pre[MAXN], suf[MAXN];
priority_queue<ll> q;
int main() {
scanf("%lld %d %d", &v, &n, &m);
for (int i = 1; i <= n; i++)
scanf("%lld %lld", &a[i].v, &a[i].w);
sort(a + 1, a + n + 1);
ll sum = 0;
if (m & 1) {
// 奇数
int mid = m >> 1;
for (int i = 1; i <= n; i++) {
pre[i] = sum;
sum += a[i].w;
q.push(a[i].w);
if (q.size() > mid) {
sum -= q.top();
q.pop();
}
}
while (!q.empty())
q.pop();
sum = 0;
for (int i = n; i; i--) {
suf[i] = sum;
sum += a[i].w;
q.push(a[i].w);
if (q.size() > mid) {
sum -= q.top();
q.pop();
}
}
for (int i = n - mid; i > mid; i--)
if (pre[i] + suf[i] + a[i].w <= v) {
printf("%lld", a[i].v);
return 0;
}
} else {
// 偶数
int mid = m >> 1;
for (int i = 1; i <= n; i++) {
sum += a[i].w;
q.push(a[i].w);
if (q.size() > mid) {
sum -= q.top();
q.pop();
}
pre[i] = sum;
// 注意这一句的位置有所调整
}
while (!q.empty())
q.pop();
sum = 0;
for (int i = n; i; i--) {
sum += a[i].w;
q.push(a[i].w);
if (q.size() > mid) {
sum -= q.top();
q.pop();
}
suf[i] = sum;
}
for (int i = n - mid; i >= mid; i--)
if (pre[i] + suf[i + 1] <= v) {
// 统计答案也有所调整
printf("%lld", (a[i].v + a[i + 1].v) >> 1);
return 0;
}
}
return 0;
}
```
[例题](https://ac.nowcoder.com/acm/problem/20185) 此题为 **内存调度题型** 的模板题。意思就是说：CPU 只能调用 cache，然而 cache 大小是有限的，需要优化 cache 调度使得访问主存时发生缺失的次数最少。
此题的贪心思路是：访问时间越靠后，就越先把它删掉。这样做来，堆需要维护的就是 cache 内主存的下一次访问时间。每次访问新的主存时，先看它在不在 cache 里面，如果在就直接访问；否则，就将堆顶元素对应的主存删掉，然后把当前内存块加进去，`ans++` 即可。
```cpp
// https://ac.nowcoder.com/acm/problem/20185
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n, m;
int a[MAXN], b[MAXN], last[MAXN], nex[MAXN];
int cnt = 0, ans = 0;
bool in_cache[MAXN];
priority_queue<int> q;
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
}
sort(b + 1, b + n + 1);
int n2 = unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b + 1, b + n2 + 1, a[i]) - b;
// 可以用 lower_bound() 离散化
// 注意 a[i] = lower_bound(...) - b - 1 是错的
nex[last[a[i]]] = i;
last[a[i]] = i;
// 建链表
}
for (int i = 1; i <= n2; i++) {
nex[last[i]] = n + i;
a[n + i] = i;
}
// 这里是处理最后一次访问
// a[i] 保存的是第 i 次访问的主存编号
for (int i = 1; i <= n; i++) {
while (!q.empty() && !in_cache[a[q.top()]])
q.pop();
if (in_cache[a[i]]) {
q.push(nex[i]);
continue;
}
// while() 与 if() 需要一起理解
// 在 cache 内的情况
if (cnt < m) {
in_cache[a[i]] = true;
cnt++, ans++;
q.push(nex[i]);
// cache 内还有可用空间
} else {
in_cache[a[q.top()]] = false;
ans++, q.pop();
in_cache[a[i]] = true;
q.push(nex[i]);
// cache 内没有可用空间
}
}
printf("%d\n", ans);
return 0;
}
```
堆的思维难度真的挺大。考场上尽量放宽思路，大胆贪心吧。
# DAY 3
## 并查集
有个东西叫做 **种类并查集**，也就是说当并查集无法满足对于关系的询问的时候，就把并查集扩大到$k\cdot n$的规模，使得每种关系都能够通过 `merge()` 来表达。这种做法要求对于关系的辨析非常明确，不然乱合并就会导致维护失败。
注意在使用种类并查集的时候，一定要 **把所有的** `fa[]` **都初始化**， 不然就凉了。
当然，对于类似二分图染色的题目（比如关押罪犯），也可以用“敌人的敌人就是朋友”的思想进行合并。不过这个思想事实上不如二分图染色易懂，所以有个概念就差不多了。
## 哈希
哈希表甚至可以用来 **维护离散化**，也就是说要查询一个数字在离散化以后对应的值的时候，可以用带权哈希去做。
# DAY 4
## 平衡树 (fhq)
`merge(x, y)` 操作需要保证 `x` 中所有的元素都比 `y` 所有的元素更小，否则就会违反 BST 的性质。所以在新建元素的时候，**只能写成** `merge(merge(x, new_node(c), y)`。
维护区间翻转的时候，需要注意 `split()` 里的 `k` 是 **要变的**，当跑到 `x` 的右子树里的时候需要把 `k -= s(l(x)) - 1`。此外，**任何步骤** 都需要考虑 `tag` 的影响，必须马上把上次的 `tag` 传下去，否则就会对接下来的步骤产生影响。
```cpp
void pushdown(int x) {
swap(l(x), r(x));
if (l(x))
f(l(x)) ^= 1;
if (r(x))
f(r(x)) ^= 1;
f(x) = false;
// 必！须！要！清！空！标！记！
return ;
}
void insert(int c) {
int x, y;
split(root, c, x, y);
root = merge(merge(x, new_node(c)), y);
return ;
}
void split(int now, int k, int &x, int &y) {
if (!now) {
x = y = 0;
return ;
}
if (f(now))
pushdown(now);
if (s(l(now)) < k) {
x = now;
split(r(x), k - s(l(x)) - 1, r(x), y);
// 注意 k 是要变的！
update(x);
} else {
y = now;
split(l(y), k, x, l(y));
update(y);
}
return ;
}
void reverse(int l, int r) {
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);
// 注意是 r - l + 1
f(y) ^= 1;
root = merge(merge(x, y), z);
return ;
}
void print(int now) {
if (!now)
return ;
if (f(now))
pushdown(now);
// 不能忘记 pushdown
print(l(now));
printf("%d ", v(now));
print(r(now));
return ;
}
// print() 操作也得注意 tag 是否下传
```
### 动态拆点
有些时候，平衡树的空间被大大浪费（比如很多节点共同维护一段连续区间），就可以把一些节点的信息合并在一起，并在需要的时候拆点，充分利用空间。
比如 [P3960](https://www.luogu.org/problem/P3960) 便可以用动态拆点的 fhq Treap 实现区间平移来水掉。
```cpp
// https://www.luogu.org/problem/P3960
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3e5 + 10;
const int SIZE = 5e6 + 10;
int n, m, q;
struct interval { ll l, r; };
struct BinarySearchTree {
int lson, rson, pri, size;
interval val;
#define l(x) tree[x].lson
#define r(x) tree[x].rson
#define v(x) tree[x].val
#define p(x) tree[x].pri
#define s(x) tree[x].size
} tree[SIZE];
int tot = 0, root[MAXN];
int my_rand() {
static int tmp = 1;
tmp = 1LL * tmp * 19260817 % 0x3f3f3f3f;
return tmp;
}
int newnode(ll l, ll r) {
tot++;
l(tot) = r(tot) = 0;
v(tot).l = l, v(tot).r = r;
p(tot) = my_rand();
s(tot) = r - l + 1;
return tot;
}
inline void update(int x) {
s(x) = s(l(x)) + s(r(x)) + v(x).r - v(x).l + 1;
}
int merge(int x, int y) {
if (!x || !y)
return x + y;
if (p(x) < p(y)) {
r(x) = merge(r(x), y);
update(x);
return x;
} else {
l(y) = merge(x, l(y));
update(y);
return y;
}
}
inline void split_new(int now, int k) {
// s(now) -> k
if (k >= v(now).r - v(now).l + 1)
return ;
int nex = newnode(v(now).l + k, v(now).r);
v(now).r = v(now).l + k - 1;
r(now) = merge(nex, r(now));
update(now);
return ;
}
// 全新动态拆点方法
void split(int now, int k, int &x, int &y) {
if (!now) {
x = y = 0;
return ;
}
if (s(l(now)) < k) {
split_new(now, k - s(l(now)));
x = now;
split(r(x), k - s(l(x)) - (v(now).r - v(now).l + 1), r(x), y);
update(x);
} else {
y = now;
split(l(y), k, x, l(y));
update(y);
}
return ;
}
inline void prework() {
for (int i = 1; i <= n; i++)
root[i] = newnode(1LL * (i - 1) * m + 1, 1LL * i * m - 1);
for (int i = 1; i <= n; i++)
root[0] = merge(root[0], newnode(1LL * i * m, 1LL * i * m));
return ;
}
inline ll work(int a, int b) {
ll res;
if (b == m) {
int x, y, z;
split(root[0], a, x, z);
split(x, a - 1, x, y);
res = v(y).l;
root[0] = merge(merge(x, z), y);
} else {
int x, y, z, x2, y2, z2;
split(root[a], b, x, z);
split(x, b - 1, x, y);
res = v(y).l;
split(root[0], a, x2, z2);
split(x2, a - 1, x2, y2);
root[a] = merge(merge(x, z), y2);
root[0] = merge(merge(x2, z2), y);
}
return res;
}
int main() {
scanf("%d %d %d", &n, &m, &q);
prework();
for (int x, y; q; q--) {
scanf("%d %d", &x, &y);
printf("%lld\n", work(x, y));
}
return 0;
}
```
# DAY 5
## 单调队列
单调队列 / 二维单调队列都是用于维护滑动窗口模型的题目。
单调队列能够维护长度不超过$k$的最大子段和，甚至环上最大子段和。具体做法是用前缀和优化，可以结合代码理解。
```cpp
// http://acm.hdu.edu.cn/showproblem.php?pid=3415
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int a[MAXN << 1], sum[MAXN << 1];
int q[MAXN << 1], head, tail;
int ans = 0, l, r;
void solve(int n, int k) {
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + a[i];
int ans = -0x3f3f3f3f;
head = tail = 0;
// 注意初始时是把 0 加入队列了的
q[head] = 0;
for (int i = 1; i <= n; i++) {
while (head <= tail && q[head] < i - k)
head++;
if (sum[i] - sum[q[head]] > ans) {
ans = sum[i] - sum[q[head]];
l = q[head] + 1, r = i;
}
while (head <= tail && sum[q[tail]] > sum[i])
tail--;
q[++tail] = i;
}
l = l > n >> 1 ? l - (n >> 1) : l;
r = r > n >> 1 ? r - (n >> 1) : r;
// 处理环上区间的性质
printf("%d %d %d\n", ans, l, r);
}
int n, k;
int main() {
int T;
scanf("%d", &T);
while (T--) {
ans = -0x3f3f3f3f;
head = 1, tail = 1;
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
solve(n << 1, k);
// 破换成链
}
return 0;
}
```
此外，单调队列能够维护的东西还有很多很多。比如斜率优化 dp，这个等到 week 3 会复习到。
## 单调栈
单调栈维护的是对于一个元素$a_i$，向某个方向走多少步才能走到一个大于$a_i$的元素。没有单调队列那么常考，考到的时候也是很容易能够看出来。
# DAY 6
## 总结
这周捡起来了很多东西。数据结构的裸题是不太可能考到的，不过碰到需要维护 / 优化某些东西的时候，它能够救人。
---
下周就去看《天气之子》啦。