Description!
Input
第一行 : 一个整数 N , 表示方案和询问的总数
接下来 N 行, 每行开头一个单词 Query 或 Project
若单词为 Query, 则后接一个整数 T, 表示 Blue Mary 询问第 T 天的最大收益
若单词为 Project, 则后接两个实数 S,P, 表示该种设计方案第一天的收益 S, 以及以后每天比上一天多出的收益 P
1 <= N <= 100000 1 <= T <=50000 0 < P < 100,| S | <= 10^6
提示: 本题读写数据量可能相当巨大, 请选手注意选择高效的文件读写方式
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 条直线, 然后询问某 x 位置的最大的 y
每次加入一条直线时, 首先判断该直线与区间所记录的直线 (记录在 Mid) 的斜率大小, 然后判断在 Mid 点时, 哪条直线的答案更优
如果是斜率大的答案更优, 那么在 (Mid,r] 内, 一定是斜率大的答案优, 因此我们只需要将斜率小的直线下放到左儿子, 并且将当前区间记录的直线更新为斜率大的直线; 如果是斜率小的答案更优, 那么在 [l,Mid] 内一定是斜率小的更优, 所以我们就将斜率大的直线传到右儿子中递归更新, 当前区间同样更新
其实读到这里应该还会有个小问题, 由于线段树上记录的是一段段的折线, 并且这些折线斜率必定递增我们在上文所说的某条直线在更新了区间记录的答案后, 就把另一条直线往一边下放了, 难道另一边不用下放吗? 又或者说, 当前记录的新直线, 不用在另一边下放, 判断一下, 更新一下吗?
标记永久化带来的这个疑问, 必然有解决的方法我们统计答案的时候, 将路过的所有直线都计算一下, 更新答案, 就不会有什么问题了
又或者我们换个思想, 每个区间所记录的直线, 只是保证 Mid 最优的直线, 那么我们的问题也就解决了
- #include < cmath > #include < cstdio > #include < cstring > #include < iostream > #include < algorithm > #define inf 0x7f7f7f7f using namespace std;
- typedef long long ll;
- typedef unsigned int ui;
- typedef unsigned long long ull;
- inline int read() {
- int x = 0,
- f = 1;
- char ch = getchar();
- for (; ch < 0 || ch > 9; ch = getchar()) if (ch == -) f = -1;
- for (; ch >= 0 && ch <= 9; ch = getchar()) x = (x << 1) + (x << 3) + ch - 0;
- return x * f;
- }
- inline void print(int x) {
- if (x >= 10) print(x / 10);
- putchar(x % 10 + 0);
- }
- const int N = 1e5,
- Day = 5e4;
- double K[N + 10],
- B[N + 10]; //K 是斜率, B 是与 y 轴交点(来自初中数学的摧残)
- int Lazy[N * 4 + 10]; // 标记记录的不是斜率, 是序号
- char s[10];#define ls(p << 1)#define rs(p << 1 | 1) bool check(int x, int y, int cnt) {
- return K[x] * (cnt - 1) + B[x] > K[y] * (cnt - 1) + B[y];
- } // 位于 cnt 点的两直线判断
- void change(int p, int l, int r, int t) {
- if (l == r) {
- if (check(t, Lazy[p], l)) Lazy[p] = t;
- return;
- }
- int mid = (l + r) >> 1;
- if (K[t] > K[Lazy[p]]) { // 将判断对照前面的文字说明便十分明了
- if (check(t, Lazy[p], mid)) change(ls, l, mid, Lazy[p]),
- Lazy[p] = t;
- else change(rs, mid + 1, r, t);
- }
- if (K[t] < K[Lazy[p]]) {
- if (check(t, Lazy[p], mid)) change(rs, mid + 1, r, Lazy[p]),
- Lazy[p] = t;
- else change(ls, l, mid, t);
- }
- }
- double get(int x, int cnt) {
- return K[x] * (cnt - 1) + B[x];
- } // 得到 cnt 点的答案
- double query(int p, int l, int r, int t) {
- if (l == r) return get(Lazy[p], t);
- int mid = (l + r) >> 1;
- double ans = get(Lazy[p], t); // 一路更新答案
- if (t <= mid) ans = max(ans, query(ls, l, mid, t));
- if (t > mid) ans = max(ans, query(rs, mid + 1, r, t));
- return ans;
- }
- int main() {
- int n = read(),
- cnt = 0;
- for (int i = 1; i <= n; i++) {
- scanf("%s", s + 1);
- if (s[1] == P) {
- cnt++;
- scanf("%lf%lf", &B[cnt], &K[cnt]);
- change(1, 1, Day, cnt); // 题目并未告诉你明确的天数, 因此只能这么玩
- }
- if (s[1] == Q) {
- int x = read();
- double t = query(1, 1, Day, x);
- printf("%d\n", (int) t / 100); // 按题目要求输出
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2487622.html