题目链接

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*/