题目分析

这是一个动态线性函数最大值查询问题。每个金融顾问的方案对应一个线性函数：

$$f_i(t) = S_i + P_i \cdot (t-1) = P_i \cdot t + (S_i - P_i) $$

需要支持：

• 添加线性函数：Project S P
• 查询某天所有函数最大值：Query T

---

算法思路：李超线段树

函数转换

将收益函数重写为：

$$f(t) = k \cdot t + b$$

其中：

• $k = P$（日增长量）
• $b = S - P$（截距调整）

李超线段树核心

• 线段树区间 $[1, R]$ 对应天数 $1$ 到 $R=50000$
• 每个节点存储当前区间中点处值最大的线段
• 插入时递归更新可能更优的线段
• 查询时遍历路径上的所有候选线段

---

代码解析

线段插入

void upd(int l, int r, int p, int v) {
    if(!s[p]) return s[p] = v, void();
    
    int mid = l + r >> 1;
    int &u = s[p];
    
    if(calc(mid, u) < calc(mid, v)) swap(u, v);
    
    if(calc(l, u) < calc(l, v)) upd(l, mid, p<<1, v);
    if(calc(r, u) < calc(r, v)) upd(mid+1, r, p<<1|1, v);
}

单点查询

db qry(int l, int r, int p, int x) {
    if(!s[p]) return 0;
    if(l == r) return calc(x, s[p]);
    
    int mid = l + r >> 1;
    db res = calc(x, s[p]);
    
    if(x <= mid) 
        return max(res, qry(l, mid, p<<1, x));
    else
        return max(res, qry(mid+1, r, p<<1|1, x));
}

---

复杂度分析

• 插入操作：$O(\log^2 R)$
• 查询操作：$O(\log R)$
• 总复杂度：$O(N \log^2 R)$，在 $N \leq 10^5$ 时可行

---

输出处理

查询结果需要精确到整百元：

db q = qry(1, R, 1, x);
q = q / 100;
cout << (int)q << "\n";  // 直接截断小数部分

---

样例验证

输入：

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
...

处理过程：

• 添加多个线性函数
• 查询时计算各函数在该天的值并取最大值
• 结果除以 $100$ 后取整

输出：全部为 0，说明在样例数据中所有查询天的最大收益均小于 $100$。

---

算法优势

• 高效动态维护：支持在线添加函数和查询
• 空间优化：仅存储 $O(R)$ 空间
• 正确性保证：李超线段树确保找到真正最大值

该解法通过李超线段树高效解决了动态线性函数最大值查询问题。