1568: [JSOI2008]Blue Mary开公司

题目描述

传送门

题目分析

简单分析可以发现就是不停给出了\(n\)条直线，要求每次给出一条直线后求出所有直线在横坐标为\(x\)时\(y\)的最大值。

李超树裸题。

不知道李超树的可以移步百度。

是代码呢

#include <bits/stdc++.h>using namespace std;#define ls rt<<1#define rs rt<<1|1#define mid ((l+r)/2)const int MAXN=5e5+7;int n,m,st[MAXN],tr[MAXN<<2];double a[MAXN<<2],b[MAXN<<2];char opt[20];inline int pd(int x,int y,int pos){return a[x]+(pos-1)*b[x]>a[y]+(pos-1)*b[y];}inline void change(int l,int r,int rt,int x){ ???if(l==r){ ???????if(pd(x,tr[rt],l)) tr[rt]=x; ???????return; ???} ???if(b[x]>b[tr[rt]]) ???????if(pd(x,tr[rt],mid)) change(l,mid,ls,tr[rt]),tr[rt]=x; ???????else change(mid+1,r,rs,x); ???if(b[x]<b[tr[rt]]) ???????if(pd(x,tr[rt],mid)) change(mid+1,r,rs,tr[rt]),tr[rt]=x; ???????else change(l,mid,ls,x);}inline double getans(int k,int x){return a[k]+(x-1)*b[k];}inline double query(int l,int r,int rt,int x){ ???if(l==r) return getans(tr[rt],x); ???double ans=getans(tr[rt],x); ???if(x<=mid) ans=max(ans,query(l,mid,ls,x)); ???else ans=max(ans,query(mid+1,r,rs,x)); ???return ans;}int main(){ ???scanf("%d",&n); ???for(int i=1;i<=n;i++){ ???????scanf("%s",opt); ???????if(opt[0]=='P'){ ???????????++m; scanf("%lf%lf",&a[m],&b[m]); ???????????change(1,500005,1,m); ???????} else { ???????????int x;scanf("%d",&x); ???????????printf("%d\n", (int)query(1,500005,1,x)/100); ???????} ???}}

1568: [JSOI2008]Blue Mary开公司

原文地址：https://www.cnblogs.com/victorique/p/10384493.html