题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=1568
https://www.luogu.org/problemnew/show/P4254
思路
超哥线段树模板题
若当前线段完全高于标记线段，则将当前线段进行标记
若当前线段完全低于标记线段，则将当前线段扔掉
若当前线段与标记线段有交点，考虑在上面的一部分是一个两条线段形成的分段函数，将长的线段作为当前节点的标记，短的线段继续下放
代码
#include <iostream>#include <cstdio>#define ls rt<<1#define rs rt<<1|1using namespace std;const int N=1e5+7;int read() { ???int x=0,f=1;char s=getchar(); ???for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; ???for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; ???return x*f;}int tr[N<<2];double a[N],b[N];double f(int x,int l) {return a[x]*l+b[x];}int cmp(int x,int y,int r) {return f(x,r)>=f(y,r);}void modify(int l,int r,int k,int rt) { ???if(l==r) { ???????if(cmp(k,tr[rt],l)) tr[rt]=k; ???????return; ???} ???int mid=(l+r)>>1; ???if(a[k]>a[tr[rt]]) ???????if(cmp(k,tr[rt],mid)) ???????????modify(l,mid,tr[rt],ls),tr[rt]=k; ???????else ???????????modify(mid+1,r,k,rs); ???if(a[k]<a[tr[rt]]) ???????if(cmp(k,tr[rt],mid)) ???????????modify(mid+1,r,tr[rt],rs),tr[rt]=k; ???????else ???????????modify(l,mid,k,ls);}double query(int l,int r,int L,int rt) { ???if(l==r) return f(tr[rt],L); ???int mid=(l+r)>>1; ???double ans=0; ???if(L<=mid) return max(f(tr[rt],L),query(l,mid,L,ls)); ???else return max(f(tr[rt],L),query(mid+1,r,L,rs));}int main() { ???int n=read(); ???char s[10]; ???for(int i=1;i<=n;++i) { ???????scanf("%s",s); ???????if(s[0]=='Q') { ???????????int id=read(); ???????????printf("%d\n",(int)(query(1,n,id,1))/100); ???????} else { ???????????scanf("%lf%lf",&b[i],&a[i]); ???????????b[i]-=a[i]; ???????????modify(1,n,i,1); ???????} ???} ???return 0;}/*100Query 30Project 5.52800 0.96000Query 24Project -409.19200 18.24000Project -209.51200 13.24800Project -2.15200 2.88000Query 20Project 0.15200 2.49600Query 340002*/bzoj1568 [JSOI2008]Blue Mary开公司
原文地址：https://www.cnblogs.com/dsrdsr/p/10356215.html