zhoujinchong2004 @ 2025-10-22 21:10:55

一、问题数学建模

1.1 问题本质

这是一个带修改的历史区间覆盖统计问题，核心在于高效统计动态变化的区间对历史查询的贡献。

问题形式化

给定：

$n$ 个路灯，初始状态为 $s_1, s_2, \ldots, s_n$ （0或1）
$q$ 个操作，每个操作发生在时刻 $1, 2, \ldots, q$

可达性定义：

站点 $a$ 到站点 $b$ 可达，当且仅当路灯 $a, a+1, \ldots, b-1$ 全部亮起
等价于：存在一个连续亮灯区间 $[l, r]$ 使得 $l \le a$ 且 $r \ge b-1$

两种操作：

toggle $i$ ：切换路灯 $i$ 的状态
query $a$ $b$ ：统计从时刻 $0$ 到当前时刻，有多少个时刻满足 $a$ 到 $b$ 可达

目标：对每个查询输出答案。

1.2 关键观察

观察 1：连续区间的维护

命题：在任意时刻，所有亮起的路灯可以划分为若干个极大连续区间。

示例：

路灯状态: 1 1 0 1 1 1 0 0 1
连续区间: [1,2]  [4,6]    [9,9]

维护策略：使用 set<pair<int,int>> 动态维护所有极大连续区间。

观察 2：区间的时间生命周期

每个连续区间 $[l, r]$ 有一个存在时间段 $[t_{\text{start}}, t_{\text{end}}]$ ：

区间在时刻 $t_{\text{start}}$ 被创建或扩展
区间在时刻 $t_{\text{end}}$ 被删除或缩小

贡献计算：

区间 $[l, r]$ 在时间段 $[t_1, t_2]$ 存在
对所有满足 $l \le a$ 且 $r \ge b-1$ 的查询 $(a, b)$ ，贡献值为 $t_2 - t_1$

观察 3：二维平面转化

将问题转化为二维平面上的操作：

横轴：查询的左端点 $a$
纵轴：查询的右端点 $b-1$

矩形贡献：

区间 $[l, r]$ 在时间 $[t_1, t_2]$ 存在
对矩形 $[1, l] \times [r, n]$ 内的所有查询点贡献 $t_2 - t_1$

查询：

query $(a, b)$ 等价于查询点 $(a, b-1)$ 的累计贡献

1.3 朴素算法的瓶颈

方法 1：暴力模拟

// 对每个查询
for (每个查询 (a, b) 在时刻 t_q) {
    int count = 0;
    for (时刻 t = 1 到 t_q) {
        // 检查时刻 t 的状态
        bool ok = true;
        for (int i = a; i < b; i++) {
            if (!lamp[i][t]) {
                ok = false;
                break;
            }
        }
        if (ok) count++;
    }
    输出 count;
}

复杂度分析：

每个查询： $O(q \times n)$
总复杂度： $O(q^2 \times n) \approx 3 \times 10^{15}$ ❌ 超时

二、核心算法思想

2.1 关键观察：区间的动态维护

toggle 操作对区间的影响

情况 1：路灯从灭到亮

可能与左右相邻区间合并

切换前: [1,2] _ [4,5]
toggle 3
切换后: [1,5]

情况 2：路灯从亮到灭

可能将一个区间分裂为两个

切换前: [1,5]
toggle 3
切换后: [1,2] [4,5]

使用 set 维护区间

set<pair<int, int>> st;  // 存储所有极大连续亮灯区间

// toggle 路灯 x
if (a[x] == 0) {  // 从灭到亮
    // 检查左右邻居
    auto it = st.upper_bound({x, INF});
    int l = x, r = x;
    
    if (前驱区间的右端点 == x-1) {
        合并到前驱区间;
        l = 前驱区间的左端点;
    }
    
    if (后继区间的左端点 == x+1) {
        合并到后继区间;
        r = 后继区间的右端点;
    }
    
    st.insert({l, r});
} else {  // 从亮到灭
    找到包含 x 的区间 [l, r];
    删除区间 [l, r];
    
    if (l < x) st.insert({l, x-1});
    if (r > x) st.insert({x+1, r});
}

2.2 关键观察二：矩形加与二维数点

问题转化

区间存在的时间贡献：

区间 $[l, r]$ 从时刻 $t_1$ 到 $t_2$ 存在
对所有满足 $l \le a \le n$ 且 $x \le b-1 \le r$ 的查询 $(a, b-1)$ 贡献 $t_2 - t_1$

二维平面表示：

矩形 $[l, n] \times [1, r]$ 加上权值 $t_2 - t_1$
查询点 $(a, b-1)$ 的值

二维差分优化

矩形 $[l_x, r_x] \times [l_y, r_y]$ 加 $val$ 可以用四个角点实现：

point(lx, ly, +val)
point(lx, ry+1, -val)
point(rx+1, ly, -val)
point(rx+1, ry+1, +val)

原理：二维前缀和的逆运算

$$\text{sum}(x, y) = \sum_{i \le x, j \le y} \text{point}(i, j) $$

2.3 关键观察三：CDQ 分治

CDQ 分治思想

目标：处理修改和查询的依赖关系。

分治策略：

将操作序列 $[l, r]$ 分为两部分 $[l, mid]$ 和 $[mid+1, r]$
计算左半部分的修改对右半部分查询的贡献
递归处理左右两部分

关键性质：

左半部分的修改一定在右半部分的查询之前
可以按第一维排序后，用树状数组维护第二维

算法流程

CDQ(l, r):
    if l == r: return
    
    mid = (l + r) / 2
    
    // 左半部分的修改对右半部分查询的贡献
    按 x 坐标排序
    for 右半部分的查询 i:
        将所有 x <= query[i].x 的左半部分修改加入树状数组
        query[i].ans += 树状数组查询(y 坐标)
    
    清空树状数组
    
    // 递归处理
    CDQ(l, mid)
    CDQ(mid+1, r)

三、算法流程详解

3.1 数据结构定义

模块 1：基础数据结构

const int N = 300005;

// 路灯状态
bool a[N];  // a[i]: 路灯 i 是否亮起

// 连续区间集合
set<pair<int, int>> st;  // 存储所有极大连续区间 (l, r)

// 操作节点
struct node {
    int x, y;     // 坐标 (x, y)
    int val;      // 权值或查询编号
    bool tp;      // 类型：0=修改，1=查询
};

node o[N * 5];    // 当前操作数组
node _o[N * 5];   // 原始操作数组（备份）
int ans[N * 5];   // 查询答案

模块 2：树状数组

struct BIT {
    int tr[N];
    
    // 单点加
    void add(int x, int val) {
        for (int i = x; i <= n; i += i & -i)
            tr[i] += val;
    }
    
    // 前缀和查询
    int ask(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i)
            res += tr[i];
        return res;
    }
} T;

作用：维护第二维（y坐标）的前缀和。

3.2 矩形加操作

模块 3：二维差分

int m = 0;  // 操作总数

// 矩形 [lx, rx] × [ly, ry] 加 val
void add(int lx, int rx, int ly, int ry, int val) {
    // 左下角 +val
    o[++m] = {lx, ly, val, 0};
    
    // 右下角外 -val
    o[++m] = {rx+1, ly, -val, 0};
    
    // 左上角外 -val
    o[++m] = {lx, ry+1, -val, 0};
    
    // 右上角外 +val
    o[++m] = {rx+1, ry+1, val, 0};
}

示例：

区间 [2,5] 在时间 [0,3] 存在（共3个时刻）
对矩形 [1,2] × [5,n] 贡献 3

调用: add(1, 2, 5, n, 3)

3.3 区间维护与时间贡献

模块 4：初始化区间

// 读入初始状态
string s;
cin >> s;

st.insert({-INF, -INF});  // 哨兵

for (int i = 1; i <= n; i++) {
    a[i] = s[i-1] - '0';
    
    if (a[i]) {
        // 尝试与前一个区间合并
        auto [l, r] = *st.rbegin();
        
        if (r == i - 1) {
            // 合并：删除旧区间，插入新区间
            st.erase({l, r});
            st.insert({l, i});
        } else {
            // 新区间
            st.insert({i, i});
        }
    }
}

// 初始区间从时刻 0 到 q 都存在
for (auto [l, r] : st) {
    if (l == -INF) continue;
    add(l, n, 1, r, q);  // 对矩形 [l,n]×[1,r] 贡献 q
}

st.insert({INF, INF});  // 哨兵

关键点：

初始时刻记为时刻 0
初始区间对所有 $q$ 个时刻都有贡献

模块 5：toggle 操作

for (int i = 1; i <= q; i++) {
    string op;
    cin >> op;
    
    if (op == "toggle") {
        int x;
        cin >> x;
        a[x] ^= 1;  // 切换状态
        
        int l, r;
        
        if (a[x]) {  // 从灭到亮
            // 查找前驱和后继区间
            auto nx = st.upper_bound({x, INF});
            auto pr = nx; --pr;
            
            l = r = x;
            
            // 与前驱合并
            if ((*pr).second == x - 1) {
                l = (*pr).first;
                st.erase(pr);
            }
            
            // 与后继合并
            if ((*nx).first == x + 1) {
                r = (*nx).second;
                st.erase(nx);
            }
            
            st.insert({l, r});
        } else {  // 从亮到灭
            // 找到包含 x 的区间
            auto it = st.upper_bound({x, INF});
            --it;
            l = (*it).first;
            r = (*it).second;
            st.erase(it);
            
            // 分裂区间
            if (l < x) st.insert({l, x-1});
            if (r > x) st.insert({x+1, r});
        }
        
        // 记录区间的时间贡献
        int val = q - i;  // 剩余时间
        if (!a[x]) val = -val;  // 熄灭时是负贡献
        
        add(l, x, x, r, val);
    }
}

贡献计算：

路灯 $x$ 亮起：区间 $[l, r]$ 在时刻 $i$ 之后都存在，贡献 $+(q-i)$
路灯 $x$ 熄灭：区间 $[l, r]$ 在时刻 $i$ 之后都不存在，贡献 $-(q-i)$

模块 6：query 操作

if (op == "query") {
    int a, b;
    cin >> a >> b;
    b--;  // 转换为路灯编号
    
    // 记录查询点
    o[++m] = {a, b, m, 1};  // tp=1 表示查询
    
    // 特判：当前时刻的状态
    auto lt = st.upper_bound({a, INF});
    auto rt = st.upper_bound({b, INF});
    
    // 检查 a 和 b 是否在同一个区间内
    if (lt == rt && lamp[a] && lamp[b]) {
        ans[m] -= q - i;  // 减去后续时刻的贡献
    }
}

特判原因：

查询在时刻 $i$ ，但我们统计的是时刻 $0$ 到 $i$ 的贡献
如果当前时刻 $a$ 和 $b$ 在同一区间，需要减去 $i+1$ 到 $q$ 的多余贡献

3.4 CDQ 分治处理

模块 7：CDQ 主流程

void CDQ(int l, int r) {
    // 恢复原始顺序
    for (int i = l; i <= r; i++)
        o[i] = _o[i];
    
    // 递归边界
    if (l == r) return;
    
    int mid = (l + r) >> 1;
    
    // 按 x 坐标排序
    sort(o + l, o + mid + 1, cmp);        // 左半部分
    sort(o + mid + 1, o + r + 1, cmp);    // 右半部分
    
    // 双指针扫描
    int j = l - 1;
    for (int i = mid + 1; i <= r; i++) {
        // 将所有 x <= o[i].x 的修改加入树状数组
        while (j < mid && o[j+1].x <= o[i].x) {
            j++;
            if (!o[j].tp) {  // 修改操作
                T.add(o[j].y, o[j].val);
            }
        }
        
        // 查询操作
        if (o[i].tp) {
            ans[o[i].val] += T.ask(o[i].y);
        }
    }
    
    // 清空树状数组
    while (j >= l) {
        if (!o[j].tp) {
            T.add(o[j].y, -o[j].val);
        }
        j--;
    }
    
    // 递归处理
    CDQ(l, mid);
    CDQ(mid + 1, r);
}

流程说明：

恢复顺序：每次递归开始时恢复原始时间顺序
排序：左右两部分分别按 $x$ 坐标排序
双指针：维护所有 $x \le \text{query}_x$ 的修改
树状数组：查询 $y$ 坐标的前缀和
清空：撤销树状数组的修改
递归：分别处理左右两部分

3.5 主函数流程

模块 8：输入与调用

int main() {
    cin >> n >> q;
    
    // 初始化区间（模块 4）
    初始化连续区间();
    
    // 处理操作（模块 5、6）
    for (int i = 1; i <= q; i++) {
        处理 toggle 或 query 操作();
    }
    
    // 备份操作数组
    for (int i = 1; i <= m; i++)
        _o[i] = o[i];
    
    // CDQ 分治
    CDQ(1, m);
    
    // 输出答案
    for (int i = 1; i <= m; i++) {
        if (_o[i].tp) {  // 查询操作
            cout << ans[i] << "\n";
        }
    }
    
    return 0;
}

四、复杂度分析

4.1 时间复杂度

区间维护

操作	复杂度	说明
`set` 插入/删除	$O(\log n)$	每个 toggle 最多 3 次操作
toggle 总复杂度	$O(q \log n)$	$q$ 次操作

CDQ 分治

递归树分析：

深度： $O(\log m)$ ，其中 $m = O(q)$
每层复杂度：
- 排序： $O(m \log m)$
- 树状数组操作：每个修改/查询 $O(\log n)$ ，共 $O(m \log n)$

总复杂度：

$$T(m) = 2T(m/2) + O(m \log m + m \log n) = O(m \log^2 m + m \log m \log n) $$

简化为：

O(q \log^2 q)

数值估算：

3 \times 10^5 \times 18^2 \approx 10^8

4.2 空间复杂度

数据结构	大小	说明
`o[]`, `_o[]`	$O(q)$	每个 toggle 产生 4 个点，每个 query 产生 1 个点
`set`	$O(n)$	最多 $n$ 个区间
`BIT`	$O(n)$	树状数组

总空间复杂度： $O(n + q)$

五、算法优化技巧

优化 1：哨兵节点

st.insert({-INF, -INF});  // 左哨兵
st.insert({INF, INF});    // 右哨兵

作用：避免查找前驱/后继时的边界判断。

优化 2：位运算优化

// 状态切换
a[x] ^= 1;

// lowbit
inline int lowbit(int x) { return x & -x; }

优化 3：恢复数组

// 每次递归开始时恢复原始顺序
for (int i = l; i <= r; i++)
    o[i] = _o[i];

原因：CDQ 分治会多次排序，需要保持原始时间顺序。

优化 4：特判优化

// 查询时检查当前状态
if (lt == rt && a[l] && a[r]) {
    ans[m] -= q - i;
}

作用：减少不必要的计算。

六、易错点提醒

易错点 1：区间合并的判断

// ❌ 错误：未检查相邻性
if (存在前驱区间) {
    合并;  // 可能不相邻
}

// ✅ 正确：检查相邻
if ((*pr).second == x - 1) {
    合并;
}

易错点 2：时间贡献的符号

// ❌ 错误：未考虑灭灯的负贡献
int val = q - i;
add(l, x, x, r, val);

// ✅ 正确：灭灯时取负
int val = q - i;
if (!a[x]) val = -val;
add(l, x, x, r, val);

易错点 3：查询坐标的转换

// ❌ 错误：未转换为路灯编号
query a b
o[++m] = {a, b, m, 1};

// ✅ 正确：b-1 是最后一个需要亮的路灯
query a b
b--;
o[++m] = {a, b, m, 1};

易错点 4：CDQ 中的树状数组清空

// ❌ 错误：未清空树状数组
CDQ(l, mid);
CDQ(mid+1, r);  // 树状数组还有残留值

// ✅ 正确：回滚所有修改
while (j >= l) {
    if (!o[j].tp)
        T.add(o[j].y, -o[j].val);
    j--;
}

易错点 5：二维差分的边界

// ❌ 错误：边界错误
add(lx, rx, ly, ry, val) {
    o[++m] = {rx, ry, val, 0};  // 应该是 rx+1, ry+1
}

// ✅ 正确：外侧边界要 +1
o[++m] = {rx+1, ry+1, val, 0};

七、算法设计思想总结

7.1 问题转化

原问题：动态区间覆盖统计 转化为：二维平面上的矩形加、单点查询

转化过程：

连续区间 → 矩形覆盖范围
时间段 → 矩形权值
查询 → 单点累计

7.2 分治思想

核心理念：将修改和查询的时间依赖关系通过分治处理。

优势：

避免复杂的在线数据结构（如二维线段树）
利用排序优化第一维
利用树状数组优化第二维

7.3 数据结构的选择

需求	数据结构	复杂度
维护连续区间	`set`	$O(\log n)$
二维前缀和	CDQ + BIT	$O(\log^2 n)$
单点查询	树状数组	$O(\log n)$

ID

3831

时间

2000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

zhoujinchong2004

1 条题解