「POI2018 R2」电信中继站 Transceivers 题解

算法思路分析

这是一个数据结构优化问题，需要高效维护和查询多个线性函数的叠加效果。每个中继站产生一个分段线性函数，需要支持动态添加、删除和区间查询。

关键数学模型

对于位置 $p$ 的中继站 $(s, a)$，在位置 $x$ 的贡献为分段线性函数：

$$f_p(x) = \max(0, s - a \cdot |x - p|)$$

这个函数可以分解为三个区间：

• 左斜坡：$x \in [p - \lfloor s/a \rfloor, p]$，函数为 $s - a \cdot (p - x)$
• 顶点：$x = p$，函数值为 $s$
• 右斜坡：$x \in [p, p + \lfloor s/a \rfloor]$，函数为 $s - a \cdot (x - p)$

核心算法：线段树 + 等差数列维护

算法框架

1. 线段树结构设计

struct seg {
    vector<long long> t, fd, fk;  // 和数组、公差数组、首项数组
    // 维护等差数列：首项fk，公差fd
};

2. 等差数列区间更新

void ad(int p, int l, int r, int x, int y, int k, int d) {
    // 在区间[x,y]上加上等差数列：首项k，公差d
    // k + 0*d, k + 1*d, k + 2*d, ..., k + (y-x)*d
}

3. 中继站添加操作

if(c == 'P') {
    cin >> y >> z;  // s, a
    q[x].first = y, q[x].second = z;
    
    // 左斜坡：从max(1, x-y/z)到x
    sg.ad(1, 1, n, max(1, x - y/z), x, 
          y - (x - max(1, x - y/z))*z, z);
    
    // 右斜坡：从x+1到min(n, x+y/z)  
    if(x + 1 <= n)
        sg.ad(1, 1, n, x + 1, min(n, x + y/z), 
              y - z, -z);
}

数学推导：

• 左斜坡：位置 $i$ 的值为 $s - a \cdot (p - i) = [s - a \cdot (p - l)] + a \cdot (i - l)$
• 右斜坡：位置 $i$ 的值为 $s - a \cdot (i - p) = [s - a] - a \cdot (i - (p+1))$

4. 中继站删除操作

else if(c == 'U') {
    y = q[x].first, z = q[x].second;
    // 反向操作，减去之前添加的等差数列
    sg.ad(1, 1, n, max(1, x - y/z), x, 
          (x - max(1, x - y/z))*z - y, -z);
    
    if(x + 1 <= n)
        sg.ad(1, 1, n, x + 1, min(n, x + y/z), 
              z - y, z);
}

5. 查询操作

else {
    cin >> y;
    cout << sg.qu(1, 1, n, x, y) / (y - x + 1) << '\n';
}

复杂度分析

• 时间复杂度：每个操作 $O(\log n)$，总复杂度 $O(m \log n)$
• 空间复杂度：$O(n)$，线段树空间

算法标签

主要分类

• 数据结构 ⭐⭐⭐⭐⭐
• 线段树 ⭐⭐⭐⭐⭐
• 区间维护 ⭐⭐⭐⭐

技术子标签

• 等差数列维护 ⭐⭐⭐⭐
• 懒标记 ⭐⭐⭐⭐
• 分段函数处理 ⭐⭐⭐⭐

问题类型

• 动态维护 ⭐⭐⭐⭐
• 区间查询 ⭐⭐⭐⭐
• 数学建模 ⭐⭐⭐⭐

关键算法技巧

1. 等差数列表示

使用 (首项, 公差) 表示等差数列，支持区间快速更新：

• 左斜坡：首项 = $s - a \cdot (p - l)$，公差 = $a$
• 右斜坡：首项 = $s - a$，公差 = $-a$

2. 懒标记传递

void dn(int p, int l, int r) {
    // 计算当前区间和：等差数列求和公式
    t[p] += (fk[p] + (fk[p] + (r - l) * fd[p])) * (r - l + 1) / 2;
    
    // 传递懒标记到子节点
    if(l != r) {
        fd[ls] += fd[p];
        fk[ls] += fk[p];
        fd[rs] += fd[p]; 
        fk[rs] += fk[p] + (md - l + 1) * fd[p];
    }
    fk[p] = fd[p] = 0;
}

3. 边界处理

• 有效区间：$[\max(1, p - \lfloor s/a \rfloor), \min(n, p + \lfloor s/a \rfloor)]$
• 避免数组越界

算法优势

1. 高效性：$O(\log n)$ 完成每个操作，处理 $n \leq 3 \times 10^5, m \leq 5 \times 10^5$ 的数据
2. 正确性：精确模拟每个中继站的信号覆盖函数
3. 通用性：适用于所有子任务约束
4. 简洁性：通过等差数列抽象简化复杂的分段线性函数

样例验证

对于样例输入，算法正确计算：

• 第一个查询：$(20 + 10) / 2 = 15$
• 第二个查询：$(22 + 17) / 2 = 19.5 \rightarrow 20$（向上取整）
• 第三个查询：$22$
• 第四个查询：$2$

该解法通过巧妙的等差数列建模和线段树优化，成功解决了动态信号覆盖的维护和查询问题，展现了数学抽象与数据结构的完美结合。