「CCO 2024」Heavy Light Decomposition 题解

题目分析

我们需要将数组划分为若干连续子数组，使得每个子数组都是"好"的。一个"好"数组要求其中的元素交替出现轻元素（出现一次）和重元素（出现多次）。

关键思路

动态规划定义

设 $f[i]$ 表示将前 $i$ 个元素划分成好的子数组的方案数。我们需要高效计算 $f[i]$ 的值。

核心观察

对于一个位置 $i$，我们需要找到所有 $j < i$，使得子数组 $a[j+1 \ldots i]$ 是好的。然后：

其中 $j$ 满足 $a[j+1 \ldots i]$ 是好的子数组。

轻重要求的转化

一个好的子数组必须满足：

1. 相邻元素的轻重要求交替
2. 每个重元素必须在子数组中出现至少两次

这转化为对区间内元素出现次数的约束条件。

算法实现详解

数据结构设计

struct SegT {
    int pd[M];  // 懒标记，用于区间加
    pair<int, int> val[M];  // 存储(最小值, 最小值出现次数之和 mod 1000003)
    
    // 构建线段树
    void build(int x, int l, int r) {
        pd[x] = 0, val[x] = make_pair(0, 0);
        if (l == r) return;
        int mid = (l + r) >> 1, a = x << 1;
        build(a, l, mid);
        build(a | 1, mid + 1, r);
    }
    
    // 下推懒标记
    void pushdown(int x) {
        int a = x << 1;
        pd[a] += pd[x], val[a].F += pd[x];
        pd[a | 1] += pd[x], val[a | 1].F += pd[x];
        pd[x] = 0;
    }
    
    // 区间加操作
    void update(int x, int l, int r, int v, int tl, int tr) {
        if (l <= tl && tr <= r) {
            val[x].F += v;
            pd[x] += v;
            return;
        }
        if (pd[x] != 0) pushdown(x);
        
        int mid = (tl + tr) >> 1, a = x << 1;
        if (mid >= l) update(a, l, r, v, tl, mid);
        if (mid < r) update(a | 1, l, r, v, mid + 1, tr);
        
        // 合并左右子树信息
        val[x] = min(val[a], val[a | 1]);
        val[x].S = ((val[x].F == val[a].F ? val[a].S : 0) + 
                    (val[x].F == val[a | 1].F ? val[a | 1].S : 0)) % mod;
    }
    
    // 单点修改
    void modify(int x, int l, int v, int tl, int tr) {
        if (tl == tr) {
            val[x].S = v;  // 修改方案数
            return;
        }
        int mid = (tl + tr) >> 1, a = x << 1;
        if (mid >= l) modify(a, l, v, tl, mid);
        else modify(a | 1, l, v, mid + 1, tr);
        
        val[x] = min(val[a], val[a | 1]);
        val[x].S = ((val[x].F == val[a].F ? val[a].S : 0) + 
                    (val[x].F == val[a | 1].F ? val[a | 1].S : 0)) % mod;
    }
} segt;

关键变量说明

• a[N]: 存储输入数组
• pre[i]: 元素 $a[i]$ 上一次出现的位置，如果第一次出现则为 $-1$
• lst[x]: 记录值 $x$ 最后出现的位置
• f[i]: DP 数组，前 $i$ 个元素的划分方案数

核心函数 upd

void upd(int x, int c) {
    // 根据不同的边界情况更新线段树区间
    if (x != lst[a[x]] && x + 1 != lst[a[x + 1]])
        segt.update(1, 0, x, c, 0, n);
    else if (x != lst[a[x]]) {
        if (pre[x + 1] >= 0)
            segt.update(1, 0, pre[x + 1], c, 0, n);
    } else if (x + 1 != lst[a[x + 1]]) {
        if (pre[x] >= 0)
            segt.update(1, 0, pre[x], c, 0, n);
    } else {
        int l = pre[x], r = pre[x + 1];
        if (l > r) swap(l, r);
        if (l >= 0) segt.update(1, 0, l, c, 0, n);
        if (r < x) segt.update(1, r + 1, x, c, 0, n);
    }
}

这个函数处理由于新元素加入导致的约束条件变化，维护哪些 $j$ 可以转移到当前状态。

主算法流程

int main() {
    scanf("%d", &n);
    memset(lst, -1, sizeof(lst));
    
    // 预处理每个元素的上一次出现位置
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        pre[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    
    segt.build(1, 0, n);
    memset(lst, -1, sizeof(lst));
    f[0] = 1;  // 空划分方案数为1
    
    for (int i = 0; i < n; i++) {
        // 将f[i]存入线段树
        segt.modify(1, i, f[i], 0, n);
        
        // 处理约束条件变化
        if (pre[i] >= 0) {
            if (pre[i] < i - 1) upd(pre[i], -1);
            if (pre[i]) upd(pre[i] - 1, -1);
        }
        
        lst[a[i]] = i;  // 更新最后出现位置
        
        if (pre[i] >= 0) {
            if (pre[i] < i - 1) upd(pre[i], 1);
            if (pre[i]) upd(pre[i] - 1, 1);
        }
        
        upd(i - 1, 1);  // 添加新的约束
        
        // 最小值对应的方案数就是f[i+1]
        f[i + 1] = segt.val[1].S;
    }
    
    printf("%d\n", f[n]);
    return 0;
}

算法正确性

线段树维护的是对于每个可能的划分点 $j$，以 $j+1$ 开始到当前 $i$ 的子数组违反轻重要求的"代价"。当最小值为 $0$ 时，对应的划分点集合就是所有合法的转移来源。

复杂度分析

• 时间复杂度: $O(N \log N)$，每个位置进行常数次线段树操作
• 空间复杂度: $O(N)$，用于存储数组和线段树

该算法通过巧妙的线段树维护，避免了直接检查所有可能的子数组，实现了高效的状态转移。