NCC-79601 Captain's Log

NCC-79601 Captain's Log

To boldly go where no one has gone before.

【复习笔记】Week 1 数据结构

posted on 2019-10-22 23:16:34 | under 复习笔记 |

DAY 1

线段树

有些时候线段树维护的是 贪心 出来的东西,比如:维护 $\frac {a[i]-a[j]}{i-j}$的最大值,支持单点修改。经过论证,此处的最大值只可能在 $i-j=1$的情况下取得(画图可证),因此只用线段树维护差分序列即可。

此题 中线段树甚至可以用于实现 类似平衡树 的功能,具体为维护区间最大值,然后进行线段树上的分层二分查找。

树状数组

二维 树状数组的写法:

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 可以帮助水完许多题目,因此有关堆的题目思维难度都很大。很多时候,题目需要用到 贪心 思想来建堆。

比如 例题: 有 $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 减小。因此,直接贪心地将堆顶换为当前任务的用时即可。

#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$大 / 小数的和。

比如 例题:选 $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[] 维护的是闭区间,在统计答案的时候稍作调整即可。

// 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;
}

例题 此题为 内存调度题型 的模板题。意思就是说:CPU 只能调用 cache,然而 cache 大小是有限的,需要优化 cache 调度使得访问主存时发生缺失的次数最少。

此题的贪心思路是:访问时间越靠后,就越先把它删掉。这样做来,堆需要维护的就是 cache 内主存的下一次访问时间。每次访问新的主存时,先看它在不在 cache 里面,如果在就直接访问;否则,就将堆顶元素对应的主存删掉,然后把当前内存块加进去,ans++ 即可。

// 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 传下去,否则就会对接下来的步骤产生影响。

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 便可以用动态拆点的 fhq Treap 实现区间平移来水掉。

// 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$的最大子段和,甚至环上最大子段和。具体做法是用前缀和优化,可以结合代码理解。

// 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

总结

这周捡起来了很多东西。数据结构的裸题是不太可能考到的,不过碰到需要维护 / 优化某些东西的时候,它能够救人。


下周就去看《天气之子》啦。