题目大意
每次给整个区间内加入一个一次函数,求单点最大值。
Code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define RG register int
#define LL long long
const int Index=50010;
double k[100010],b[100010];
int SegTree[200010];
int N,Num=0;
inline double f(int ID,int x){return k[ID]*(x-1)+b[ID];}
void Update(int Root,int L,int R,int ID){
if(L==R){
if(f(ID,L)>f(SegTree[Root],L))
SegTree[Root]=ID;
return;
}
int mid=(L+R)>>1;
if(k[ID]>k[SegTree[Root]]){
if(f(ID,mid)>f(SegTree[Root],mid)){
Update(Root<<1,L,mid,SegTree[Root]);
SegTree[Root]=ID;
}
else Update(Root<<1|1,mid+1,R,ID);
}
else if(k[ID]<k[SegTree[Root]]){
if(f(ID,mid)>f(SegTree[Root],mid)){
Update(Root<<1|1,mid+1,R,SegTree[Root]);
SegTree[Root]=ID;
}
else Update(Root<<1,L,mid,ID);
}
return;
}
double Query(int Root,int L,int R,int x){
if(L==R) return f(SegTree[Root],x);
int mid=(L+R)>>1;
if(x<=mid) return max(f(SegTree[Root],x),Query(Root<<1,L,mid,x));
return max(f(SegTree[Root],x),Query(Root<<1|1,mid+1,R,x));
}
int main(){
char opt[20];
scanf("%d",&N);
for(RG i=1;i<=N;++i){
scanf("%s",opt);
if(opt[0]=='Q'){
int x;scanf("%d",&x);
printf("%d\n",(int)(Query(1,1,Index,x)/100.0));
}
else{
++Num;
scanf("%lf%lf",&b[Num],&k[Num]);
Update(1,1,Index,Num);
}
}
return 0;
}