题意

这道题相当于是插入n条直线y=kx+b
然后查询某x位置所有直线中的最大值。

题解

网上说是什么超哥线段树。。
于是乎赶紧学了一发。。
其实也不是很难。。
你就在每一个节点维护一个左右儿子都有可能成为答案的直线。。
然后扫下去求最大
具体看代码

小小的建议

你可以在对拍的时候把整百位去掉。。
要不你会发现小数据很多0

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
const int M=50000;
int n;
double a[N],b[N];
int m;//当前的线段到哪里
int tr[N*2];//这个节点所用的最优值 
bool Jud (int x,int y,int pos)//x在pos这个位置时否比y优 
{return a[x]+b[x]*(pos-1)>a[y]+b[y]*(pos-1);
}
void change (int now,int l,int r,int x)//在哪个节点 区间 现在要插入编号为x的线段 
{if (l==r){if (Jud(x,tr[now],l))tr[now]=x;return ;}int mid=(l+r)>>1;if (b[x]>b[tr[now]])//这个斜率大{if (Jud(x,tr[now],mid))//看下在这个点是否已经超过了，若是，那么右端点的就都没了change(now<<1,l,mid,tr[now]),tr[now]=x;//记录一下这个还是有可能成为答案的elsechange(now<<1|1,mid+1,r,x);}   else{if (Jud(x,tr[now],mid))change(now<<1|1,mid+1,r,tr[now]),tr[now]=x;else change(now<<1,l,mid,x);}
}
double get (int x,int pos)
{return a[x]+b[x]*(pos-1);
}
double getmax (int now,int l,int r,int x)
{if (l==r)   return get(tr[now],x);int mid=(l+r)>>1;double ans=get(tr[now],x);if (x<=mid) ans=max(ans,getmax(now<<1,l,mid,x));else ans=max(ans,getmax(now<<1|1,mid+1,r,x));return ans;
}
int main()
{scanf("%d",&n);for (int u=1;u<=n;u++){char ss[20];scanf("%s",ss);if (ss[0]=='P'){m++;scanf("%lf%lf",&a[m],&b[m]);change(1,1,M,m);}else{int x;scanf("%d",&x);double t=getmax(1,1,M,x);// printf("%lf\n",t);int k=t;printf("%d\n",k/100);}}   return 0;
}