P4254 [JSOI2008] Blue Mary 开公司

题目背景

Blue Mary 最近在筹备开一家自己的网络公司。由于他缺乏经济头脑，所以先后聘请了若干个金融顾问为他设计经营方案。

题目描述

万事开头难，经营公司更是如此。开始的收益往往是很低的，不过随着时间的增长会慢慢变好。也就是说，对于一个金融顾问 \(i\)，他设计的经营方案中，每天的收益都比前一天高，并且均增长一个相同的量 \(P_i\)。

由于金融顾问的工作效率不高，所以在特定的时间，Blue Mary 只能根据他已经得到的经营方案来估算某一时间的最大收益。由于 Blue Mary 是很没有经济头脑的，所以他在估算每天的最佳获益时完全不会考虑之前的情况，而是直接从所有金融顾问的方案中选择一个在当天获益最大的方案的当天的获益值，例如：

有如下两个金融顾问分别对前四天的收益方案做了设计：

在第一天，Blue Mary 认为最大收益是 \(2\)（使用顾问 2 的方案），而在第三天和第四天，他认为最大收益分别是 \(9\) 和 \(13\)（使用顾问 1 的方案）。而他认为前四天的最大收益是：\(2 + 5 + 9 + 13 = 29\)。

现在你作为 Blue Mary 公司的副总经理，会不时收到金融顾问的设计方案，也需要随时回答 Blue Mary 对某天的“最大收益”的询问（这里的“最大收益”是按照 Blue Mary 的计算方法）。一开始没有收到任何方案时，你可以认为每天的最大收益值是 0。下面是一组收到方案和回答询问的例子：

• 询问 \(2\)，回答 \(0\)。
• 收到方案：\(0\ 1\ 2\ 3\ 4\ 5\ \cdots\)
• 询问 \(2\)，回答 \(1\)。
• 收到方案：\(2\ 2.1\ 2.2\ 2.3\ 2.4\ \cdots\)
• 询问 \(2\)，回答 \(2.1\)。

输入格式

第一行 ：一个整数 \(N\)，表示方案和询问的总数。

接下来 \(N\) 行，每行开头一个单词 Query 或 Project。

若单词为 Query，则后接一个整数 \(T\)，表示 Blue Mary 询问第 \(T\) 天的最大收益。

若单词为 Project，则后接两个实数 \(S, P\)，表示该种设计方案第一天的收益 \(S\)，以及以后每天比上一天多出的收益 \(P\)。

输出格式

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

Solution:

模拟赛场切了这题，这是很好的

我们先将题目翻译一下：在线的给你一些线段，对于一个给定的x坐标求在此坐标时最大的y

显然，李超线段树模板题
我们数据结构选手又来看什么都像板子了

但这回是真的板子：

至于李超线段树详解吗
_{当然是先咕咕咕了}
国庆一定写

首先我们先说一下李超线段树要维护的是什么东西：区间内中点的最大值，也就是说，当前线段树节点[l,r]上挂的那一条线段是能使得在当前区间中点mid处y值最大的那一条。
但是很显然的一种情况是：区间中点最大并不能保证区间所有点最大，这时我们就需要在update函数上下功夫，也是我认为整个李超树最精髓的一部分：

假设先前线段树上挂的直线为id,现在要插入一条直线k。
如果两条直线没有交点，那么很显然将下面的那一条直接扔掉然后留上面的那条
如果两条直线有交点：

那么显然，在mid处，直线k要高于直线id,然而在此区间的右半部分，id仍可能有贡献，此时我们就需要将区间[l,r]的直线改为k,然后将直线id下放至[mid+1,r]进行更新，直到出现两直线无交点为止
(注：两直线指的是区间内原来挂的直线和下放更新的直线，父亲区间内的直线和子区间内的直线一般不会是同一条)

其他的情况基本都可以通过上图所描述的情况推理得出而且及其相似，这里不过多赘述
_{虽然我每写一次就要重推一次就是了}

然后我们再来说一下query:上文说了update的运作方式，我们发现了一个小问题：既然只有当有线段插入并且和父区间原线段有交点时才会有线段被下放到子区间，那么在线段很少的情况下，那子区间不是空的吗？你真的不需要pushdown吗?

_{既然这不是普通的线段树，那么它的query肯定也不是普通的query}:
我们在query时，并不需要等到l==r时才统计答案，而是从[1,n]一直统计到[pos,pos],这样做一方面是为了省下pushdown所带来的时间消耗，另一方面从逻辑上也更容易思考：
根据前面对于update函数的描述我们发现一个性质:所有左右两端都比线段树上的直线低的线段一定不在线段树上，也就是说，在一个区间[l,r]内，它的所有子区间内的直线都和他有交点，而那些 “不优” 的直线是根本不可能出现在线段树上的，所以我们在查询的时候从
[1,n]一直查到[pos,pos],的正确性是显然的

还有一个补充说明：那你这样写update,只要有交点就更新，那时间复杂度难道不会很差吗？

(放学了先咕着)

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,m,cnt;
char c[999];
struct line{
 double k,b;
}q[N];
double h(int x,int id)
{
 if(id==0)return -998244353.9;
 double k=q[id].k,b=q[id].b;
 return 1.0*x*k+b;
}
//Segment_Tree
#define ls x<<1
#define rs x<<1|1
struct Tree{
 int l,r,id;
 double val;
}t[N<<2];
void build(int x,int l,int r)
{
 t[x].l=l,t[x].r=r;
 if(l==r)return ;
 int mid=l+r>>1;
 build(ls,l,mid);
 build(rs,mid+1,r);
}
void upd(int x,int k)
{
 int id=t[x].id,l=t[x].l,r=t[x].r,mid=t[x].l+t[x].r>>1;
 if(h(l,id)<h(l,k)&&h(r,id)<h(r,k))
 {
 t[x].id=k;
 return ;
 }
 if(h(l,id)<h(l,k))
 {
 if(h(mid,id)<h(mid,k)){upd(rs,id);t[x].id=k;}
 else{upd(ls,k);}
 }
 if(h(r,id)<h(r,k))
 {
 if(h(mid,id)<h(mid,k)){upd(ls,id);t[x].id=k;}
 else{upd(rs,k);}
 }
}
void query(int x,int pos,double &res)
{
 res= h(pos,t[x].id) > res ? h(pos,t[x].id) : res;
 if(t[x].l==t[x].r)return;
 int mid=t[x].l+t[x].r>>1;
 if(pos<=mid)query(ls,pos,res);
 if(mid<pos) query(rs,pos,res);
}
void work()
{
 cin>>n;
 build(1,1,50000);
 for(int i=1,x;i<=n;i++)
 {
 scanf("%s",c);
 if(c[0]=='Q')
 {
 double ans=-998244353;
 scanf("%d",&x);
 x--;
 query(1,x,ans);
 x=max((int)(ans/100),0);
 printf("%d\n",x);
 }
 else
 {
 double k,b;
 scanf("%lf%lf",&b,&k);
 q[++cnt]=(line){k,b};
 upd(1,cnt);
 }
 }
}
int main()
{
 //freopen("company.in","r",stdin);freopen("company.out","w",stdout);
 work();
 return 0;
}