李超树（斜率优化无脑DS）

如果我们需要一个数据结构来维护多个线段在一个点上的最值，那我们就可以使用李超树来完成这个事情。李超树的每个区间记录的是中点值最大的一条线段。
如何做到呢？
1、插入
step1：
首先根据我们的定义，每个区间要保留中点值最大的一条线，所以将老线段的中点值跟新线端的中点值比较取大的一个。如果老线段的中点值要小一些就跟新线端swap一下，保证新线端中点值更小。
step2：
考虑下传，
下传时有两种情况，一种情况是老线段斜率更小，所以在右边会和老线段有交，另一种情况是新线段斜率更小那么新线段可能在左侧与老线段有交。所以新线段只需要更新一侧即可。

2、查询
只需要不断比对线段即可。
注意：可能需要动态开点。
模板题 P4254 [JSOI2008]Blue Mary开公司

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e5 + 10, M = 5e4 + 10;
int q, n;
#define db double
// double k[N], b[N];
struct Seg {
	db k, b;
} s[N];

inline db w(int id, int pos) {
	return s[id].k * (pos - 1.0) + s[id].b;
}

int rt = 0;
struct Segment_Tree {
	int tot = 0;
	struct info {
		int id;
	} a[M << 4];
	#define lson (pos << 1)
	#define rson (pos << 1 | 1)

	inline void modify(int pos, int l, int r, int p) {
		int mid = l + r >> 1;
		if (!pos) ++tot;
		if (w(p, mid) > w(a[pos].id, mid)) 
			swap(p, a[pos].id);
		if (l == r) return ;
		if (s[p].k < s[a[pos].id].k) modify(lson, l, mid, p);
		else modify(rson, mid + 1, r, p);
	}

	inline db query(int pos, int l, int r, int p) {
		if (l == r) {
			return w(a[pos].id, p);
		}
		int mid = l + r >> 1;
		db res = w(a[pos].id, p);
		if (p <= mid)chkmax(res, query(lson, l, mid, p));
		else chkmax(res, query(rson, mid + 1, r, p));
		return res;
	}
} sgt;

int main(){
	//FO("");
	read(q);
	while (q--) {
		char type[10];
		int t;
		scanf ("%s", type);
		if (type[0] == 'P') {
			++n;
			scanf ("%lf %lf", &s[n].b, &s[n].k);
			sgt.modify(1, 1, M - 5, n);
		}
		else {
			read(t);
			printf ("%.0f\n", floor (sgt.query (1, 1, M - 5, t) / 100.0));
		}
	}
	return 0;
}