洛谷ACloj50求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
struct _{
	double k,b;
}l[100005];
int n,tree[200005],cnt;
void add(double k,double b){
	l[++cnt] = {k,b};
}
int ls(int x){
	return x << 1;
}
int rs(int x){
	return x << 1 | 1;
}
int calc(int X,double x){
	return l[X].k * x + l[X].b;
}
void modify(int x,int l,int r,int X){
	if (!tree[x]){
		tree[x] = X;
		return;
	}
	int mid = l + r >> 1;
	if (calc(X,mid) > calc(tree[x],mid)) swap(tree[x],X);
	if (l == r) return;
	if (calc(X,l) > calc(tree[x],l)) modify(ls(x),l,mid,X);
	if (calc(X,r) > calc(tree[x],r)) modify(rs(x),mid + 1,r,X);
}
double query(int x,int l,int r,int v){
    if (!tree[x]) return log(0);
	double ans = calc(tree[x],v);
	if (l == r) return ans;
	int mid = l + r >> 1;
	if (v <= mid) ans = max(ans,query(ls(x),l,mid,v));
	else ans = max(ans,query(rs(x),mid + 1,r,v));
	return ans;
}
main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin >> n;
    while (n--){
        string s;
        double x,y;
        int t;
        cin >> s;
        if (s[0] == 'Q'){
        	cin >> t;
        	cout << max(0ll,(int)((query(1,1,50000,t) / 100))) << "\n";
		}
        else{
            cin >> x >> y;
            add(y,x - y);
            modify(1,1,50000,cnt);
        }
    }
	return 0;
}