[JSOI2008]Blue Mary开公司

时间：2023-01-21 22:08:36

Description

[JSOI2008]Blue Mary开公司

Input

第一行 ：一个整数N ，表示方案和询问的总数。 
接下来N行，每行开头一个单词“Query”或“Project”。 
若单词为Query，则后接一个整数T，表示Blue Mary询问第T天的最大收益。 
若单词为Project，则后接两个实数S，P，表示该种设计方案第一天的收益S，以及以后每天比上一天多出的收益P。
1 <= N <= 100000 1 <= T <=50000 0 < P < 100，| S | <= 10^6 
提示：本题读写数据量可能相当巨大，请选手注意选择高效的文件读写方式。

Output

对于每一个Query，输出一个整数，表示询问的答案，并精确到整百元（以百元为单位，
例如：该天最大收益为210或290时，均应该输出2）。没有方案时回答询问要输出0

Sample Input

10
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000

Sample Output

0
0
0
0
0
李超线段树模板题
 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 struct Line

 {

   double b,k;

 }line,tree[];

 char s[];

 double ans;

 int n,N=;

 int i;

 bool pd(Line a,Line b,double x)

 {

   return (a.k*(x-)+a.b>b.k*(x-)+b.b);

 }

 double cal(Line a,double x)

 {

   return a.k*(x-)+a.b;

 }

 void update(int rt,int l,int r,Line x)

 {

   if (l==r)

     {

       if (pd(x,tree[rt],l))

     tree[rt]=x;

       return;

     }

   int mid=(l+r)/;

   if (x.k>tree[rt].k)

     {

       if (pd(x,tree[rt],mid)) update(rt<<,l,mid,tree[rt]),tree[rt]=x;

       else update(rt<<|,mid+,r,x);

     }

   if (x.k<tree[rt].k)

     {

       if (pd(x,tree[rt],mid)) update(rt<<|,mid+,r,tree[rt]),tree[rt]=x;

       else update(rt<<,l,mid,x);

     }

 }

 double query(int rt,int l,int r,int x)

 {

   if (l==r)

     {

       return cal(tree[rt],l);

     }

   int mid=(l+r)/;

   ans=max(ans,cal(tree[rt],x));

   if (x<=mid) ans=max(ans,query(rt<<,l,mid,x));

   else ans=max(ans,query(rt<<|,mid+,r,x));

   return ans;

 }

 int main()

 {int T;

   cin>>n;

   for (i=;i<=n;i++)

     {

       scanf("%s",s);

       if (s[]=='P')

     {

       scanf("%lf%lf",&line.b,&line.k);

       update(,,N,line);

     }

       else

     {

       scanf("%d",&T);

       ans=;

       ans=query(,,N,T);

       printf("%d\n",(int)ans/);

     }

     }

 }

相关文章