算法实战：机器人摧毁墙壁最大数目的线段树与离散化方案

问题描述

一条无限长的直线上分布着一些机器人和墙壁。给定整数数组 robots、distance 和 walls：

• robots[i] 是第 i 个机器人的位置。
• distance[i] 是第 i 个机器人的子弹可以行进的最大距离。
• walls[j] 是第 j 堵墙的位置。

每个机器人有一颗子弹，可以向左或向右发射，最远距离为 distance[i] 米。子弹会摧毁其射程内路径上的每一堵墙。机器人是固定的障碍物：如果子弹在到达墙壁前击中另一个机器人，它会立即在该机器人处停止，无法继续前进。

返回机器人可以摧毁墙壁的最大数量。注意：墙壁和机器人可能在同一位置；该位置的墙壁可以被该位置的机器人摧毁。机器人不会被子弹摧毁。

示例： 输入：robots = [4,10], distance = [3,5], walls = [1,2,7,10] 输出：3 解释：机器人 0 向左覆盖 [1, 4]，摧毁墙 1；机器人 1 向左覆盖 [5, 10]，摧毁墙 7 和 10。

核心难点分析

这道题的直观解法似乎很容易想到动态规划，但有两个主要坑点：

1. 坐标范围过大：坐标可达 10^9，直接开数组会导致内存超限（MLE）。
2. 重叠统计：两个机器人的射击范围可能重叠，需要避免重复计算被摧毁的墙壁。

思路一：线段树 + 离散化

由于坐标空间巨大，我们首先需要对关键坐标进行离散化。关键坐标包括所有机器人的位置和墙壁的位置。

状态定义

设 dp[i] 表示处理到第 i 个机器人时，能摧毁的最大墙壁数。为了处理左右射击的依赖关系，我们需要维护一个线段树来查询区间最大值。

转移方程推导

假设当前机器人在 x2，向左能打到 x1，向右能打到 x3。

• 向左射击：如果选择向左，它可能会与前一个向右射击的机器人产生冲突。我们需要确保不重复统计中间区域的墙。
• 向右射击：同理，需考虑与前一个机器人的边界。

利用前缀墙数 g(x) 表示位置 ≤ x 的墙的数量，我们可以将区间墙数转化为差值形式。例如，[x1, x2] 之间的墙数为 g(x2) - g(x1)。

状态转移的核心在于最大化 dp[x] - g(x) 的值，这可以通过线段树维护区间最大值来实现。

代码实现要点

1. 离散化类：封装排序、去重及映射逻辑。
2. 线段树：支持单点更新和区间查询最大值。
3. 主逻辑：按机器人位置排序后遍历，利用二分查找确定每个机器人实际可覆盖的离散化区间。

template <class T = int>
class CDiscretize {
public:
    CDiscretize(vector<T> nums) {
        sort(nums.(), nums.());
        nums.((nums.(), nums.()), nums.());
        m_nums = nums;
         ( i = ; i < nums.(); i++) {
            m_mValueToIndex[nums[i]] = i;
        }
    }
     []( T value)  {
         it = m_mValueToIndex.(value);
         (m_mValueToIndex.() == it)  ;
         it->second;
    }
    {  m_mValueToIndex.(); }
    vector<T> m_nums;
:
    unordered_map<T, > m_mValueToIndex;
};

 < ,  >
  {
:
    = ;
    = ;
    = ;
};

 < ,  >
  :  CSingeUpdateLineTree<TSave, TRecord> {
:
    ( iEleSize, TSave tDefault)
        : (iEleSize), (iEleSize * , tDefault), (tDefault) {}
    
    {
        (, , m_iEleSize - , index, update);
    }
    
    {
         (leftIndex, rightIndex, m_tDefault);
    }
    
    {  m_save[]; }

:
     m_iEleSize;
    {
         (iSaveLeft == iSaveRight) {
            ->(m_save[iNodeNO], iSaveLeft, update);
            ;
        }
          mid = iSaveLeft + (iSaveRight - iSaveLeft) / ;
         (iUpdateNO <= mid)
            (iNodeNO * , iSaveLeft, mid, iUpdateNO, update);
        
            (iNodeNO *  + , mid + , iSaveRight, iUpdateNO, update);
        ->(m_save[iNodeNO], m_save[iNodeNO * ], m_save[iNodeNO *  + ], iSaveLeft, iSaveRight);
    }
    
    {
         ((iSaveLeft >= iQueryLeft) && (iSaveRight <= iQueryRight)) {
            ->(ans, m_save[iNodeNO]);
            ;
        }
          mid = iSaveLeft + (iSaveRight - iSaveLeft) / ;
         (mid >= iQueryLeft)
            (ans, iNodeNO * , iSaveLeft, mid, iQueryLeft, iQueryRight);
         (mid +  <= iQueryRight)
            (ans, iNodeNO *  + , mid + , iSaveRight, iQueryLeft, iQueryRight);
    }
    
    vector<TSave> m_save;
     TSave m_tDefault;
};

 < ,  >
  :  CVectorSingUpdateLineTree<TSave, TRecord> {
:
     CVectorSingUpdateLineTree<TSave, TRecord>::CVectorSingUpdateLineTree;
:
    {
        ans = (ans, cur);
    }
    {
        save = (save, updatee);
    }
    {
        par = (left, r);
    }
};

  {
:
    {
         N = robots.();
        
        vector<pair<, >> rd;
        (walls.(), walls.());
         tmp = walls;
        tmp.(INT_MIN / ); 
         ( i = ; i < N; i++) {
            rd.(robots[i], distance[i]);
            tmp.(robots[i]);
        }
        
        ;
         (& i : walls) {
            i = disc[i];
        }
        (rd.(), rd.());
        
        vector<tuple<, , >> m_xs;
         M = disc.m_nums.();
        
         ( i = ; i < N; i++) {
             & [pos, dis] = rd[i];
              iLeftRobot = i ? rd[i - ].first : ;
              iLeft = (iLeftRobot, pos - dis);
              iRightRobot = (i +  == N) ? (INT_MAX / ) : rd[i + ].first;
              iRight = (iRightRobot, pos + dis);
            
              x1 = (disc.m_nums.(), disc.m_nums.(), iLeft) - disc.m_nums.();
              x2 = disc[pos];
              x3 = (disc.m_nums.(), disc.m_nums.(), iRight) - disc.m_nums.() - ;
            m_xs.(x1, x2, x3);
        }
        
        ;
        ;
        
         ( & [x1, x2, x3] : m_xs) {
            
              g2 = (walls.(), walls.(), x2) - walls.();
              g3 = (walls.(), walls.(), x3) - walls.();
              cnt1 = (walls.(), walls.(), x2) - (walls.(), walls.(), x1);
              cnt2 = (walls.(), walls.(), x3) - (walls.(), walls.(), x2);
            
              left = maxTree.(, x1 - ) + cnt1;
              right = maxTree.(, x2 - ) + cnt2;
              left2 = maxTree(x1, x2 - ) + g2;
              right2 = maxTree(x2, x3 - ) + g3;
            
            maxTree.(x2, (left, left2));
            maxTree.(x3, (right, right2));
            maxTree(x2, (left, left2) - g2);
            maxTree(x3, (right, right2) - g3);
        }
         maxTree.();
    }
};