HDU-5306 Gorgeous Sequence 解题报告

题意简述
¶

$N$ 个点的序列，编号 $0 \sim N - 1$ 。初始时，点 $i$ 的权值为 $a_{i}$ 。进行 $M$ 次如下操作：

0 x y t: 令 $a_{i} = min {a_{i}, t}$ ，其中： $x ⩽ i ⩽ y$ 。记作 $o p_{0}$
1 x y: 输出 $max {a_{i}}$ ，其中： $x ⩽ i ⩽ y$ 。记作 $o p_{1}$
2 x y: 输出 $\sum_{x ⩽ i ⩽ y} a_{i}$ 。记作 $o p_{2}$

数据范围： $1 ⩽ T ⩽ 100, 1 ⩽ \sum N, \sum M ⩽ 10^{6}$ 。

题目简析
¶

用线段树维护一段区间的 4 个标量：tag, cnt, max, sum。

max: 区间内的最大值
sum: 区间内所有值的和
tag: 一个懒惰标记, 表示在该区间执行了一次 $o p_{0}$ ，且 $t = t a g$ ；同时， $t a g = 0$ 时还表示当前节点信息未被正确更新。
cnt: 当前区间中要删除的点的个数（见下文）。

注意到修改操作 ( $o p_{0}$ ) 不会让 $a_{i}$ 变大，因此当一个数成功被修改后，它的值将始终等于 当前区间的最大值，这里的 当前区间 指的是操作中指定的区间，也是线段树中的节点。那么我们完全可以将这个数删除掉，即把这个数的权值置为 0，此后只维护当前区间的最大值信息即可。注意，我们仅删除叶子节点。

Pushup
¶

当一个叶子节点被删除时，我们要令其 $c n t = 1$ ，注意到这样一来，从当前节点到该叶子节点的路径上所有节点的信息都未被正确更新，以我们要将整条路径的 tag 置为 $0$ ^[1]；同时，要执行一次 Pushup 操作，目的是将删除后的信息正确推送给父节点。

pushup.cpp

1
2
3
4
5
void pushup(int o) {
    maxv[o] = std::max(maxv[lc], maxv[rc]);
    sumv[o] = sumv[lc] + sumv[rc];
    cntv[o] = cntv[lc] + cntv[rc];
}

Clear
¶

清零操作步骤如下：

判断当前节点的 max 值是否大于 $t$ ，若是，则不需要对该子树做修改
把当前节点 tag 置为 $0$
判断当前节点是否为叶子节点，若是则删除该节点；否则，递归 Clear 左右子树，并 Pushup

clear.cpp

1
2
3
4
5
6
7
8
9
10
11
12
void clear(int o, int tag) {
    if (maxv[o] <= tag) return;
    tagv[o] = 0;
    if (leav[o]) {
        sumv[o] = maxv[o] = 0;
        cntv[o] = 1;
    } else {
        clear(lc, tag);
        clear(rc, tag);
        pushup(o);
    }
}

Maintain
¶

再考虑维护操作。

max 的维护很简单，瞎搞下就好，问题在于 sum 的维护。由于执行 $o p_{0}$ ，实际是将一个大于 $t$ 的值变成 $t$ ，而不是删掉。这时，cnt 的作用就体现了。我们仅需执行 $s u m + = c n t \times t$ 。

maintain.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
void maintain(int o, int tag) {
    // tagv[o]==0 表示当前节点未被正确更新
    if (tagv[o]) return;

    tagv[o] = tag;          

    // 如果节点 o 维护的区间有叶子节点被删除
    if (cntv[o]) {
        sumv[o] += (LL) cntv[o] * tag;
        maxv[o] = tag;
        cntv[o] = 0;
    }
}

Update
¶

最后，更新操作就是将 待修改区间的权值比 $t$ 大的 叶子节点删除；同时，Maintain 当前区间的信息。

update.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int __ul, __ur, __uv;
void update(int o, int lft, int rht) {
    if (maxv[o] <= __uv) return;
    if (__ul<=lft and rht<=__ur) {
        clear(o, __uv);
        maintain(o, __uv);
    } else {
        int mid = mid(lft, rht);
        pushdown(o);
        if (__ul <= mid) update(lson);
        if (__ur > mid) update(rson);
        pushup(o);
    }
}

Pushdown
¶

需要注意的是，Pushdown 操作把 tag 信息下传后，当前节点的 tag 不应该置为 $0$ ，因为 $t a g = 0$ 表示当前节点的信息未被正确维护。直接调用 Maintain 维护左右子树即可。

pushdown.cpp

1
2
3
4
5
6
void pushdown(int o) {
    if (tagv[o]) {
        maintain(lc, tagv[o]);
        maintain(rc, tagv[o]);
    }
}

复杂度分析
¶

显然，单次 Update 和 Query 只会影响 $O (l o g N)$ 个节点。一开始一共有 $N$ 个节点，而单次的 Update 或 Query 操作至多产生 4 个叶子节点，而删除一个叶子节点的代价是 $O (\log N)$ ，也就是 Clear 操作，故复杂度为 $O ((N + 4 M) \log N)$ 。

空间复杂度 $O (N)$
时间复杂度 $O (N \log N)$

Hint

尽管我们得到了 $O ((N + 4 M) \log N)$ 的算法，但由于本题数据太大，还是要加一个读入优化才能通过。

题意简述¶

题目简析¶

Pushup¶

Clear¶

Maintain¶

Update¶

Pushdown¶

复杂度分析¶

Related¶