HDU-5306 Gorgeous Sequence 解题报告

目录
  1. 1. 题意简述
  2. 2. 题目简析
    1. 2.1. Pushup
    2. 2.2. Clear
    3. 2.3. Maintain
    4. 2.4. Update
    5. 2.5. Pushdown
  3. 3. 复杂度分析
  4. 4. Hint

*** 题目链接 ***
*** Code ***

题意简述

$N$ 个点的序列，编号 0~$N$-1。
初始时，点 $i$ 的权值为 $a_i$。
$M$ 次操作：

  • 0 x y t $\hskip .6em$ 令 $a_i=\min\lbrace a_i, t \rbrace$，其中：$x\leqslant i\leqslant y$。
  • 1 x y $\hskip 1.5em$ 输出 $\max\lbrace a_i \rbrace$，其中：$x\leqslant i\leqslant y$。
  • 2 x y $\hskip 1.5em$ 输出 $\displaystyle \sum\limits_{x\leqslant i\leqslant y} a_i$。

数据范围： $\displaystyle 1\leqslant T\leqslant 100; 1 \leqslant \sum N, \sum M \leqslant 10^6$。

题目简析

这是一道难题。

用线段树维护一段区间，4 个标记：tag, cnt, max, sum。
其中，max, sum 的含义显而易见。
tag 是一个懒惰标记, 表示在该区间执行了一次 操作0，且 t=tag；
同时，tag==0 时还表示当前节点信息未被正确更新。
cnt 表示当前区间中要删除的点的个数（见下文）。

注意到修改操作不会让 $a_i$ 变大，因此当一个数成功被修改后，
它的值将始终等于 ** 当前区间的最大值 **，这点很重要。
那么我们完全可以将这个数删除掉，即把这个数的权值置为 0，此后只维护当前区间的最大值信息即可。

注意，我们仅删除叶子节点。

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

Pushup

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 应该是：

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

Clear

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

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

Maintain

1
2
3
4
5
6
7
8
9
void Maintain(int o, int tag) {
    if( tagv[o]  ) return;              // tagv[o]==0 表示当前节点未被正确更新
    tagv[o] = tag;          
    if( cntv[o]  ) {                    // 如果节点 o 维护的区间有叶子节点被删除
        sumv[o] += (LL) cntv[o] * tag;
        maxv[o] = tag;
        cntv[o] = 0;
    }
}

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

Update

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 操作把 tag 信息下传后，当前节点的 tag 不应该置为 0，
因为 tag==0 表示当前节点的信息未被正确维护。
所以直接调用 Maintain 维护左右子树即可。

Pushdown

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

复杂度分析

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

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

Hint

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