比模板还模板的李超线段树题。
有一个坑：收益必须是非负的，负的也得是非负的。
特别纸张。
#include <bits/stdc++.h>
#define llong long long
#define N 100005
using namespace std;constexpr double eps = 1e-6;
inline int cmp(double a, double b){if(fabs(a-b) < eps) return 0;return a>b ? 1 : -1;
}int n;struct Seg{double k, b;bool vis;
};
inline double asky(Seg s, int x){return s.k*x+s.b;}constexpr int T = 50000;
Seg val[(T<<2)+5];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)inline void insert(Seg k, int x = 1, int l = 1, int r = T){if(!val[x].vis){val[x] = k;return;}Seg s1 = val[x], s2 = k;if(cmp(asky(s1, mid), asky(s2, mid)) < 0) swap(s1, s2);val[x] = s1;if(cmp(asky(s1, l), asky(s2, l)) < 0) insert(s2, ls(x), l, mid );if(cmp(asky(s1, r), asky(s2, r)) < 0) insert(s2, rs(x), mid+1, r);return;
}
inline double query(int pos, int x = 1, int l = 1, int r = T){double res = -1e18;if(val[x].vis) res = asky(val[x], pos);if(l == r) return res;if(pos <= mid) res = max(res, query(pos, ls(x), l, mid ));else res = max(res, query(pos, rs(x), mid+1, r));return res;
}int main(){scanf("%d", &n);insert((Seg){0, 0, true});for(int i = 1; i <= n; ++i){char op[15];scanf("%s", op);if(op[0] == 'P'){Seg s;scanf("%lf %lf", &s.b, &s.k), s.b -= s.k, s.vis = true;insert(s);}if(op[0] == 'Q'){int t; double res;scanf("%d", &t);res = query(t);if(res <= -1e18) puts("0");else printf("%d\n", (int)((res+eps)/100));}}return 0;
}