CST PA3

3-4-2 Kidd

算法构思

本题需使用 Segment Tree 数据结构, 为此我们使用 tree[] 记录一条线段的权值之和, 使用 label[] 进行懒惰标记.

...
// Line 5
#define ll long long
const int MAX = 2e5;
...
// Line 9
ll tree[16 * MAX + 100]; // 使用 tree[] 来模拟一棵线段树.
ll label[16 * MAX + 100]; // 懒惰标记.
...

给出的卡牌数为 $n\in[1, 2^{31})$, 显然不可能以此作为叶节点规模建立一棵线段树; 由于给出的卡牌操作序列数为 $m\in[1, 200000]$, 其包含的端点数最多为 $400000$, 我们将这些端点排序、去重之后, 得到新的 $k$ 个端点, 记录在 arr[] 中, 并对这 $k$ 个端点和它们分出来的 $k - 1$ 个区间这个假想的扩充数组建立线段树.

...
// Line 5
#define ll long long
const int MAX = 2e5;
...
// Line 11
ll arr[2* MAX + 100]; // 对离散化的线段端点序列进行排序与去重.
ll operations[MAX + 100][3]; // 记录操作序列.
...

具体而言, 若去重排序后留下的端点为 $\{0, 2, 6, 10, 11\}$, 那么我们只需对 $\{[0, 0], [1, 1], [2, 2], [3, 5], [6, 6], [7, 9], [10, 10], [11, 10], [11, 11]\}$ 建立线段树. 同时我们为每个区间 $[a, b]$ 定义长度 $real_length(a, b) = b - a + 1$, 注意到这里出现的不合理区间 $[11, 10]$ 的长度被定义为 $0$, 一定程度上便于我们进行理解 (这相当于一个空区间).

读入数据

...
// Line 94
for (int i = 0; i < m; i++) {
    cin >> type >> x >> y;
    arr[cnt++] = x;
    arr[cnt++] = y;
    if (type == 'H') operations[i][0] = 0;
    else operations[i][0] = 1;
    operations[i][1] = x;
    operations[i][2] = y;
}
...

读入数据时, 记录下每次操作的具体内容, 并将操作序列的端点记录在 arr[] 中.

重排序与建树

使用 <stdlib.h> 中的 qsort() 函数对读入的 arr[] 序列进行排序;

// Line 22
ll uniquify_array (ll* arr, ll length) {
    int l = 0, r = 0;
    while (++r < length)
        if (arr[l] != arr[r]) arr[++l] = arr[r];
    length = ++l;
    return length;
}

使用 uniquify_array() 对有序序列 arr[] 进行去重, 参考了课件 02-D1 部分的算法.

...
// Line 107
maxcnt = 2 * cnt - 1;
...

maxcnt 即为线段树的规模大小, 无需进行初始化.

...
// Line 109
int left, right = 0;
for (int i = 0; i < m; i++) {
    left = search(arr, 0, cnt - 1, operations[i][1]) * 2;
    right = search(arr, 0, cnt - 1, operations[i][2]) * 2;
    if (operations[i][0] == 0) do_add(1, 1, maxcnt, left, right);
    else cout << do_query(1, 1, maxcnt, left, right) << endl;
}
...

在 arr 中记录排序与去重后的离散化的线段端点, 那么我们假想的扩充数组的长度为 maxcnt = 2 * cnt - 1. 对于每一次操作给出的端点 x, y, 我们通过二分查找得到其在 arr[] 中的坐标 left, right, 其在扩充数组中的对应的端点为 2 * left, 2 * right.

以下函数参数中的 k, l, r 分别代表树的编号, 编号为 k 的树的左端点, 编号为 k 的树的右端点, x, y 分别代表操作区间的左端点, 右端点.

push_down操作

// Line 39
void update(int k, int l, int r, ll num) {
    tree[k] += num * real_length(l, r, arr);
    label[k] += num;
}

update() 更新编号为 k 的树的线段和和与懒惰标记, 即此时我们不进行数据的下放, 而是以懒惰标记的形式将其暂存在 label[] 内.

// Line 45
void push_down(int k, int l, int r) {
    int mid = (l + r) / 2;
    update(left_son(k), l, mid, label[k]);
    update(right_son(k), mid + 1, r, label[k]);
    label[k] = 0;
}

push_down 操作分别更新左右子树的和与懒惰标记, 并且将自身懒惰标记置零.

翻牌操作

// Line 34
ll real_length(int l, int r, ll* arr) {
    return (arr[(r + 1) / 2] - (r % 2) - arr[l / 2] - (l % 2) + 1);
}

real_length() 线段树中两端点间的实际线段长度, 我们使用实际长度对 tree[k] 进行更新与维护.

// Line 53
void do_add(int k, int l, int r, int x, int y) {
    if (x > r || y < l) return;
    else if (x <= l && y >= r) { update(k, l, r, 1); return; }
    else {
        int mid = (l + r) / 2;
        if (label[k] != 0) push_down(k, l, r);
        if (x <= mid) do_add(left_son(k), l, mid, x, y);
        if (mid < y) do_add(right_son(k), mid + 1, r, x, y);
        tree[k] = tree[left_son(k)] + tree[right_son(k)];
    }
}

若 add 区间与子树区间不交, 直接返回;
若子树区间包含在 add 区间内, 直接更新当前子树的和与懒惰标记;
若子树区间与 add 区间相交, 那么向下递归: 若当前懒惰标记非零, 先进行懒惰标记的下放. 然后分别更新左子树 tree[left_son(k)] 与右子树 tree[right_son(k)] 的和, 最后用左右子树的和更新本身的和 tree[k].

查询操作

// Line 66
ll do_query(int k, int l, int r, int x, int y) {
    if (x > r || y < l) return 0;
    else if (x <= l && y >= r) return tree[k];
    else { 
        int mid = (l + r) / 2;
        ll sum = 0;
        if (label[k] != 0) push_down(k, l, r); 
        if (x <= mid) sum = do_query(left_son(k), l, mid, x, y);
        if (mid < y) sum += do_query(right_son(k), mid + 1, r, x, y);
        return sum;
    }
}

do_add() 与 do_query() 在逻辑上完全相同.

若 query 区间与子树区间不交, 直接返回;
若子树区间包含在 query 区间内, 直接返回当前子树的和;
若子树区间与 query 区间相交, 那么向下递归: 若当前懒惰标记非零, 先进行懒惰标记的下放. 然后分别查询左子树 tree[left_son(k)] 与右子树 tree[right_son(k)] 的和, 最后用左右子树的和更新本身的和 tree[k].

问题解决

复杂度估计

时间复杂度

读入数据后对端点使用 qsort() 进行排序, 时间复杂度为 $O(mlogm)$;

对排序后的有序数组进行去重, 时间复杂度为 $O(m)$;

每次 do_add() 操作与 do_query() 操作实际上是对整树的一次扫描, 时间复杂度正比于树高 $O(logm)$, $m$ 次操作的整体时间复杂度仍为 $O(mlog(m)).

综上, 算法总体时间复杂度为 $O(mlog(m))$.

空间复杂度

本体空间复杂度取决于操作数 m 带来的离散化后的端点数 k, 题解中使用 tree[] 与 label[] 数组模拟了一棵 Segment Tree, 整体需要的空间最坏情况仍为 $O(m)$.

本题中直接开辟了相关大小的数组存储信息,

...
// Line 6
const int MAX = 2e5;
...
// Line 9
ll tree[16 * MAX + 100]; // 使用 tree[] 来模拟一棵线段树.
ll label[16 * MAX + 100]; // 懒惰标记.
ll arr[2* MAX + 100]; // 对离散化的线段端点序列进行排序与去重.
ll operations[MAX + 100][3]; // 记录操作序列.
...