BZOJ 1568 洛谷 P4254 [JSOI2008]Blue Mary开公司(李超线段树)

Description:

万事开头难，经营公司更是如此。开始的收益往往是很低的，不过随着时间的增长会慢慢变好。也就是说，对于一个金融顾问 $i$ ，他设计的经营方案中，每天的收益都比前一天高，并且均增长一个相同的量 $P_{i}$ 。

由于金融顾问的工作效率不高，**所以在特定的时间，Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益。**由于 Blue Mary 是很没有经济头脑的，所以他在估算每天的最佳获益时完全不会考虑之前的情况，而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值，例如：

有如下两个金融顾问分别对前四天的收益方案做了设计：

第一天	第二天	第三天	第四天	$P_{i}$
顾问	1	1	5	9	13	4
顾问	2	2	5	8	11	3

在第一天，Blue Mary认为最大收益是 2（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 9 和 13（使用顾问 1 的方案）。而他认为前四天的最大收益是：
$2 + 5 + 9 + 13 = 29$
现在你作为 Blue Mary 公司的副总经理，会不时收到金融顾问的设计方案，也需要随时回答 Blue Mary 对某天的“最大收益”的询问（这里的“最大收益”是按照 Blue Mary 的计算方法）。**一开始没有收到任何方案时，你可以认为每天的最大收益值是 0。**下面是一组收到方案和回答询问的例子：

询问 2
回答 0
收到方案：0 1 2 3 4 5 ……
询问 2
回答 1
收到方案：2 2.1 2.2 2.3 2.4 ……
询问 2
回答 2.1

Input:

第一行：一个整数 $N$ ，表示方案和询问的总数。

接下来 $N$ 行，每行开头一个单词Query或Project。

若单词为Query，则后接一个整数 $T$ ，表示 Blue Mary 询问第 $T$ 天的最大收益。

若单词为Project，则后接两个实数 $S$ ， $P$ ，表示该种设计方案第一天的收益 $S$ ，以及以后每天比上一天多出的收益 $P$ 。

Output:

对于每一个Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，例如：该天最大收益为 210 或 290 时，均应该输出 2）。没有方案时回答询问要输出 0。

Sample Input:

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000

Sample Output:

0
0
0
0
0

题目链接

有 $n$ 次操作

Query t 表示询问 $x = t$ 的 $y$ 最大值
Project s p 表示添加一条 $y = p x + s$ 的直线

所以此题就是求多条直线下某横坐标上的直线最大值，那么就是李超线段树的裸题了

首先可以用线段树来维护每个横坐标下的直线最大值（线段树上每个叶子节点存储直线的 $k 、 b $ ），之后更新的时候有4种大情况

新直线比旧直线斜率大，且新直线中点在线段树区间内中点值比旧直线中点值大
新直线比旧直线斜率大，且新直线中点在线段树区间内中点值比旧直线中点值小
新直线比旧直线斜率小，且新直线中点在线段树区间内中点值比旧直线中点值大
新直线比旧直线斜率小，且新直线中点在线段树区间内中点值比旧直线中点值小

其中 $1 、 3$ 种情况可以直接将旧直线替换掉，而 $2 、 4$ 种情况需继续进行递归判断

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-9;

int Sgn(db k) {return fabs(k) < eps ? 0 : (k < 0 ? -1 : 1);}
int Cmp(db k1, db k2) {return Sgn(k1 - k2);}

struct line {db k, b;};
db F(line k, int x) {return k.k * (x - 1) + k.b;}
line max(line k1, line k2, int x) {return Cmp(F(k1, x), F(k2, x)) < 0 ? k2 : k1;}

struct seg_tree {
  public:
    struct node {
      line v;
      node(line _v = (line){0.0, 0.0}): v(_v) {}
    };

    int n;
    vector<node> tree;

    seg_tree(int _n): n(_n) {
      tree.resize(n << 2);
    }

    void Modify(int o, int l, int r, line v) {
      if (l == r) {
        if (Cmp(F(v, l), F(tree[o].v, l)) > 0) tree[o].v = v;
        return;
      }
      int m = (l + r) >> 1;
      if (Cmp(v.k, tree[o].v.k) > 0) {
        if (Cmp(F(v, m), F(tree[o].v, m)) > 0) {
          Modify(o << 1, l, m, tree[o].v);
          tree[o].v = v;
        }
        else Modify(o << 1 | 1, m + 1, r, v);
      }
      else {
        if (Cmp(F(v, m), F(tree[o].v, m)) > 0) {
          Modify(o << 1 | 1, m + 1, r, tree[o].v);
          tree[o] = v;
        }
        else Modify(o << 1, l, m, v);
      }
    }
    void Modify(line v) {
      Modify(1, 1, n, v);
    }

    node Query(int o, int l, int r, int x) {
      if (l == r) return tree[o].v;
      int m = (l + r) >> 1;
      if (x <= m) return max(tree[o].v, Query(o << 1, l, m, x).v, x);
      return max(tree[o].v, Query(o << 1 | 1, m + 1, r, x).v, x);
    }
    node Query(int x) {
      return Query(1, 1, n, x);
    }
};

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  seg_tree sgt(500005);
  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    string op; cin >> op;
    if (op == "Query") {
      int t; cin >> t;
      cout << (int)(F(sgt.Query(t).v, t) / 100.0) << endl;
    }
    else {
      db b, k; cin >> b >> k;
      sgt.Modify((line){k, b});
    }
  }
  return 0;
}