#include<bits/stdc++.h>
#define M 500005
//这里说一下 我也不知道 为什么M 500000 + 5 的时候 全是RE 只有 M 500005 的时候才能A
//(可以自己试试 - -)  有知道的可以跟我说 
using namespace std;
int n , m , tree[M * 4];//m 是当前线段总数 (也是最后一条线段的编号)
//声明 ！！！！ tree[] 里存的是当前节点 的某条线段的编号 
double k[M * 2] , b[M * 2];
//y = kx + b  对应斜率 和 纵截据 
char op[20];
double f(int w , int x){//计算对应函数 x对应y的值 <=> f(x) = kx + b
	return k[w] * (x - 1) + b[w];
}
void up(int id ,int l , int r ,int x){
	if(l == r){//如果到了叶子节点 
		if(f(x , l) > f(tree[id] , l)) tree[id] = x ;//考虑两者的函数值 
		//如果x比tree[id]还大 更换掉就行了 
		return ;
	}
	int mid = l + r >> 1 ;
	if(k[tree[id]] < k[x]){//比较斜率 
		if(f(x , mid) > f(tree[id] , mid)){//比较此时的中点 
			up(id * 2 , l , mid , tree[id]) ; tree[id] = x;
			//如果 x 这条线段的中点函数值 比当前tree[mid] 这条线段的...大
			//那就替换掉(在那之前先把tree[id] 递归下去 不然会导致线段丢失) 
		}
		else up(id * 2 + 1 , mid + 1 , r , x);//否则直接把x 递归下去就可以了 
	}
	if(k[tree[id]] > k[x]){//道理都和上面差不多 就不说了 
		if(f(x , mid) > f(tree[id] , mid)){
			up(id * 2 + 1 , mid + 1 , r , tree[id]); tree[id] = x ;
		}
		else up(id * 2 , l , mid , x) ;
	}
}
double query(int id , int l ,int r ,int x){
	if(l == r) return f(tree[id] , x);//已经到了叶子节点 
	int mid = l + r >> 1;
	if(x <= mid){//左子树 
		return max(f(tree[id] , x) , query(id * 2 , l , mid , x));
	}
	else return max(f(tree[id] , x) , query(id * 2 + 1 , mid + 1 , r , x));
	//右子树 
}
int main(){
	scanf("%d",&n);
	while(n --){
		scanf("%s",op);
		if(op[0] == 'P'){ 
		    m ++;//新的线段加入 
			scanf("%lf%lf",&b[m],&k[m]) ;
			up(1 , 1 , M , m);
		}
		else{ int x ;
			scanf("%d",&x);
		//	printf("%.6lf\n", query(1 , 1 , M , x));不要求输出这个 好扯淡= =
		    printf("%d\n",(int) (query(1 , 1 , M , x) / 100)) ;
		}
	}
	return 0;
}

C118【模板】李超线段树 P4254 [JSOI2008] Blue Mary 开公司

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
const int N=1e5+5, T=5e4+5;
struct line{
    ldb k, b;
}lines[N];
int tree[T<<2], n;
bool cmp(double x, int u, int v){
    return lines[u].k * x + lines[u].b > lines[v].k * x + lines[v].b;
}
void upd(int p, int pl, int pr, int u){
    int mid=(pl+pr)>>1, &v=tree[p];
    if(cmp(mid, u, v)) swap(u, v);
    if(pl == pr) return;
    if(cmp(pl, u, v)) upd(p<<1, pl, mid, u);
    if(cmp(pr, u, v)) upd(p<<1|1, mid+1, pr, u);
}
ldb query(int p, int pl, int pr, double x){
    int u=tree[p], mid=(pl+pr)>>1;
    ldb ret=lines[u].k * x + lines[u].b;
    if(pl == pr){
        return ret;
    }
    if(x <= mid)
        return max(query(p<<1, pl, mid, x), ret);
    else 
        return max(query(p<<1|1, mid+1, pr, x), ret);
}
int cnt;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    while(n--){
        string op;
        cin >> op;
        if(op[0] == 'P'){
            ldb x, y;
            cin >> x >> y;
            lines[++cnt] = {y, x - y};
            upd(1, 1, 5e4, cnt);
        }
        else{
            int k;
            cin >> k;
            cout << floor(query(1, 1, 5e4, k)/100.0) << '\n';
        }
    }
    return 0;
}