问题分析

我们需要统计满足以下条件的路灯对 (i, j) 的数量：

1. A[i] = A[j]（高度相同）
2. 对于所有 i < k < j，A[k] < A[i]（中间所有路灯高度都更低）

关键观察

• 只有相同高度的路灯才可能连接
• 两个相同高度的路灯能连接，当且仅当它们之间的最大值就是这个高度
• 对于每个高度值，合法的路灯对就是那些在单调栈中相邻的相同高度位置

核心思路

对于每个高度 h，维护一个单调栈，记录所有高度为 h 的路灯位置。当插入新位置时：

• 如果栈顶位置与当前位置之间的最大值等于 h，则它们可以连接
• 否则不能连接

算法步骤

1. 初始计算：

   • 对每个高度维护单调栈
   • 从左到右扫描，维护当前最大值
   • 当遇到与栈顶高度相同且中间最大值等于该高度时，计数+1

2. 更新操作：

   • 修改一个路灯高度时，重新计算受影响的区间
   • 只更新修改位置附近的有限范围（通常左右各logN个位置）
   • 利用线段树快速查询区间最大值

3. 复杂度：O((N+Q) log N)

代码框架

#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

vector<long long> count_cable(vector<int> A, vector<pair<int, int>> C) {
    int N = A.size(), Q = C.size();
    vector<long long> ans(Q + 1);
    
    // 初始计数
    ans[0] = calculate_initial(A);
    
    // 处理每个更新
    for (int i = 0; i < Q; i++) {
        int x = C[i].first, h = C[i].second;
        // 更新A[x-1] = h
        // 重新计算受影响的电缆对数
        ans[i + 1] = calculate_current(A);
    }
    
    return ans;
}

优化要点

• 使用平衡树或有序集合维护每个高度的位置
• 修改时只检查前驱后继位置的影响
• 用线段树快速查询任意区间最大值
• 利用局部性：每次修改只影响O(1)个相邻关系。