「JOI 2023 Final」现代机器 题解

题目大意

有 $N$ 条光带，初始颜色由字符串 $C$ 给出（R 表示红，B 表示蓝）。有 $M$ 个按钮，按下按钮 $j$ 会在光带 $A_j$ 上放置球并开始一系列颜色翻转和球移动操作。进行 $Q$ 次实验，每次实验按顺序按下区间 $[L_k, R_k]$ 内的按钮，求实验结束后红色光带的数量。

解题思路

核心算法：分段处理 + 线段树 + 状态压缩

该解法采用分层处理策略，结合多种数据结构来高效处理大规模数据。

算法架构

1. 预处理阶段

颜色统计预处理：

preR[0] = 0; preB[0] = 0;
for (int i = 1; i <= n; ++i) {
    preR[i] = preR[i-1]; preB[i] = preB[i-1];
    if (s[i] == 'R') preR[i]++;
    else { preB[i]++; allB[++totB] = i; }
}

• preR[i]：前 $i$ 个光带中红色数量
• preB[i]：前 $i$ 个光带中蓝色数量
• allB[]：记录所有蓝色光带的位置

后缀统计：

sufR[n+1] = 0; sufB[n+1] = 0;
for (int i = n; i >= 1; --i) {
    sufR[i] = sufR[i+1]; sufB[i] = sufB[i+1];
    if (s[i] == 'R') { sufR[i]++; allR[++totR] = n-i+1; }
}

2. 线段树维护操作序列

构建线段树：

void build(int u, int l, int r) {
    if (l == r) {
        if (a[l]-1 >= 0) 
            info[u].push_back(Info(0, a[l]-1, (a[l]+1)%(n+1)));
        info[u].push_back(Info(a[l], n, a[l]));
        return;
    }
    // 递归构建左右子树
}

信息合并：

void pull(int u) {
    for (auto [l, r, v] : info[2*u]) {
        if ((l+v)%(n+1) <= (r+v)%(n+1)) {
            updFunc(u, v, (l+v)%(n+1), (r+v)%(n+1));
        } else {
            // 处理循环边界情况
            updFunc(u, v, (l+v)%(n+1), n);
            updFunc(u, v, 0, (r+v)%(n+1));
        }
    }
}

3. 状态转移处理

关键函数 updState： 处理单个按钮操作的状态转移：

pair<int, int> updState(int bL, int bR, int pos) {
    // 根据当前位置和边界状态更新bL, bR
    // bL: 左侧红色区域大小，bR: 右侧红色区域大小
    if (pos <= bL) {
        // 在左侧红色区域内操作
        if (nowB >= pos) {
            bL = allB[preB[bL] + pos];
        } else if (nowB + bR >= pos) {
            // ... 其他情况处理
        }
    }
    // ... 其他区域的处理
    return make_pair(bL, bR);
}

4. 批量操作优化

预处理跳跃指针：

for (int i = 0; i < 19; ++i) {
    for (int j = 0; j < 19; ++j) {
        for (int u = m; u >= 1; --u) {
            if (a[u] > bL && a[u] < bR) {
                nxtP[i][j][u] = u;
            } else {
                nxtP[i][j][u] = nxtP[i][j][u+1];
            }
        }
    }
}

前缀和优化：

for (int i = 0; i < 19; ++i) {
    for (int u = 1; u <= m; ++u) {
        sumL[i][u] = sumL[i][u-1];
        if (a[u] <= bL) sumL[i][u] += (1ll * a[u]);
        // 类似处理sumR
    }
}

查询处理流程

while (qL <= qR && cntL + cntR < n) {
    // 1. 批量处理连续的安全操作
    int nowP = nxtP[bL][bR][qL] - 1;
    
    // 2. 二分查找最大可批量处理的位置
    while (L <= R) {
        // 检查是否可以批量处理到mid位置
        // 更新cntL, cntR状态
    }
    
    // 3. 处理单个关键操作
    if (qL <= qR && cntL + cntR < n) {
        auto [x, y] = updState(cntL, cntR, a[qL]);
        cntL = x; cntR = y;
        qL++;
    }
}

算法原理

状态表示

使用 (cntL, cntR) 表示当前状态：

• cntL：左侧连续的红色区域大小
• cntR：右侧连续的红色区域大小
• 中间区域的状态可以通过预处理数组推导

批量处理思想

通过预处理，可以快速判断一段连续操作是否只影响边界区域，从而进行批量处理：

• 如果操作都在当前红色边界之外，可以快速计算累积效果
• 只有遇到可能改变边界状态的操作时才逐个处理

复杂度分析

• 预处理：$O(N + M \log M)$
• 每次查询：$O(\log M + \log N)$ 的均摊复杂度
• 总复杂度：$O(Q \log M + M \log M)$

代码亮点

1. 分层处理：根据不同数据规模使用不同策略
2. 状态压缩：用边界信息表示整个状态
3. 批量优化：通过预处理实现操作序列的快速处理
4. 边界处理：细致处理各种边界情况

总结

这个解法通过巧妙的状态表示和批量处理优化，将复杂的动态过程转化为高效的计算问题。核心思想是：

1. 状态抽象：用边界信息代表整体状态
2. 预处理加速：通过预处理支持快速状态转移
3. 分层处理：结合直接模拟和批量处理

该算法能够处理 $N, M, Q \leq 1.2 \times 10^5$ 的大规模数据，是一个高效而优雅的解决方案。