【BZOJ1568】[JSOI2008]Blue Mary开公司
Description
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
题解：样例脑残系列。
我们将每一天看成点，方案看成线段，考虑用线段树维护，对于每个区间，我们记录在这段区间中最优的线段以及区间中点的最大值。如果在这段区间中新加入了一条线段，我们进行讨论：
如果新线段的两端点都比旧线段优，则直接用新线段即可；如果新线段的两端点都不如旧线段优，则直接用旧线段即可；如果新线段的一侧比旧线段优，则我们递归处理下去即可。最后用新线段在两端点处的取值以及lson和rson的最值来更新区间最值即可。
时间复杂度$O(nlogn)$
#include <cstdio>#include <cstring>#include <iostream>#include <cmath>#define lson x<<1#define rson x<<1|1using namespace std;const int maxn=100010;const int N=50000;int n;double sa[N<<2],sb[N<<2];char str[10];void updata(int l,int r,int x,double a,double b){int mid=(l+r)>>1;if(sa[x]*l+sb[x]<a*l+b&&sa[x]*r+sb[x]<a*r+b)sa[x]=a,sb[x]=b;elseif(sa[x]*l+sb[x]<a*l+b||sa[x]*r+sb[x]<a*r+b)updata(l,mid,lson,a,b),updata(mid+1,r,rson,a,b);}double query(int l,int r,int x,int a){int mid=(l+r)>>1;double ret=a*sa[x]+sb[x];if(l==r)return ret;if(a<=mid)ret=max(ret,query(l,mid,lson,a));elseret=max(ret,query(mid+1,r,rson,a));return ret;}int main(){scanf("%d",&n);int c;double a,b;while(n--){scanf("%s",str);if(str[0]==‘Q‘)scanf("%d",&c),printf("%d\n",int(floor(query(1,N,1,c)/100)));elsescanf("%lf%lf",&a,&b),updata(1,N,1,b,a-b);}return 0;}【BZOJ1568】[JSOI2008]Blue Mary开公司 线段树
原文地址：http://www.cnblogs.com/CQzhangyu/p/7898238.html