题面
好久以前听lxl讲过 咕掉了。。 竟然又遇到了
安利blog
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <complex>
#include <ctime>
#include <vector>
#define mp(x, y) make_pair(x, y)
using namespace std;
const int N = 1e5 + 5;
const int n = 5e4 + 2;
const double eps = 1e-9;
struct Line{
double k, b;
double f(double x){return k * x + b;}
}line[N];
int lsize;
struct LCSeg{
int w[N << 2];
void ins(int rt, int l, int r, int id){
if(!w[rt]){w[rt] = id; return ;}
if(l == r){
if(line[id].f(l) > line[w[rt]].f(l)) w[rt] = id;
return ;
}
int mid = l + ((r - l) >> 1);
if(line[id].k > line[w[rt]].k){
if(line[id].f(mid) > line[w[rt]].f(mid)) ins(rt << 1, l, mid, w[rt]), w[rt] = id;
else ins(rt << 1 | 1, mid + 1, r, id);
}
else {
if(line[id].f(mid) > line[w[rt]].f(mid)) ins(rt << 1 | 1, mid + 1, r, w[rt]), w[rt] = id;
else ins(rt << 1, l, mid, id);
}//这边要好好推
}
double qry(int rt, int l, int r, int x){
if(l == r) return line[w[rt]].f(x);
double res = line[w[rt]].f(x);
int mid = l + ((r - l) >> 1);
if(x <= mid) res = max(res, qry(rt << 1, l, mid, x));
else res = max(res, qry(rt << 1 | 1, mid + 1, r, x));
return res;
}
}seg;
int main(){
int T, pos; double x, y; char ss[N];
scanf("%d", &T);
while(T--){
scanf("%s", ss);
if(ss[0] == 'Q'){
scanf("%d", &pos);
double res = seg.qry(1, 1, n, pos);
printf("%d
", (int)res / 100);
}
else {
++lsize;
scanf("%lf%lf", &line[lsize].b, &line[lsize].k); line[lsize].b -= line[lsize].k;
seg.ins(1, 1, n, lsize);
}
}
return 0;
}