[JSOI2008]Blue Mary开公司 - 李超线段树

题目背景
Blue Mary 最近在筹备开一家自己的网络公司。由于他缺乏经济头脑，所以先后聘请了若干个金融顾问为他设计经营方案。

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

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

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

第一天 第二天 第三天 第四天 P_iP
i
​
顾问 1 1 5 9 13 4
顾问 2 2 5 8 11 3
在第一天，Blue Mary认为最大收益是 2（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 9 和 13（使用顾问 1 的方案）。而他认为前四天的最大收益是：

2 + 5 + 9 + 13 = 292+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
输入格式
第一行 ：一个整数 NN ，表示方案和询问的总数。

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

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

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

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

输入输出样例
输入 #1复制
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
输出 #1复制
0
0
0
0
0
说明/提示
数据范围：

1 \leq N \leq 100000, 1 \leq T \leq 50000, 0 < P < 100, |S| \leq 10^51≤N≤100000,1≤T≤50000,0<P<100,∣S∣≤10
5

提示：

本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

李超线段树裸题。（学了半年ACM了，居然才会李超线段树QAQ）。

李超线段树是什么呢？
就是维护区间所有线段在某一个x值的最大值，经常能用于dp的斜率优化。

维护和普通的线段树差不多，更新时只需要考虑以下问题：

1. 若当前插入的线段完全覆盖当前区间最优线段，直接修改。
2. 若当前插入的线段被当前区间最优线段完全覆盖，直接返回。
3. 当前插入的线段与区间最优线段有交点，且插入的线段斜率大于当前区间最优线段：考虑当前区间中点mid，若插入的大于原来的，那么mid右边一定是被插入的修改，然后我们只需要考虑左边是否修改，递归左边，修改右边即可。
4. 当前插入的线段与区间最优线段有交点，且插入的线段斜率小于当前区间最优线段：和上面同。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
//#define mid (l+r>>1)
using namespace std;
const int N=5e4+10;
int n,cnt;
double b[N<<1],k[N<<1];
struct node{
	int res;
}t[N<<2];
inline double h(int id,int x){
	return k[id]*(x-1)+b[id];
}
void change(int p,int l,int r,int x){
	if(h(x,l)>h(t[p].res,l)&&h(x,r)>h(t[p].res,r)) return void(t[p].res=x);
	if(h(t[p].res,l)>=h(x,l)&&h(t[p].res,r)>=h(x,r))	return ;
	int mid=l+r>>1;
	if(k[x]>k[t[p].res]){
		if(h(x,mid)>h(t[p].res,mid))	change(p<<1,l,mid,t[p].res),t[p].res=x;
		else	change(p<<1|1,mid+1,r,x);
	}else{
		if(h(x,mid)>h(t[p].res,mid))	change(p<<1|1,mid+1,r,t[p].res),t[p].res=x;
		else	change(p<<1,l,mid,x);
	}
}
double ask(int p,int l,int r,int x){
	if(l==r)	return h(t[p].res,x);
	int mid=l+r>>1;
	if(x<=mid)	return max(h(t[p].res,x),ask(p<<1,l,mid,x));
	else	return max(h(t[p].res,x),ask(p<<1|1,mid+1,r,x));
}
signed main(){
	scanf("%d",&n);	char op[10];
	while(n--){
		scanf("%s",op);
		if(op[0]=='Q'){
			int x;	scanf("%d",&x);	printf("%d\n",(int)(ask(1,1,N,x)/100)); 
		}else{
			cnt++;	scanf("%lf %lf",&b[cnt],&k[cnt]);	change(1,1,N,cnt);
		}
	}
	return 0;
}