题面
BZOJ https://lydsy.com/JudgeOnline/problem.php?id=1568
洛谷 https://www.luogu.org/problemnew/show/P4254
题解
是模板题啊.
- #include<iostream>
- #include<cstdio>
- using namespace std;
- #define MAX 50050
- #define lson (now<<1)
- #define rson (now<<1|1)
- int Q,n=50000;char ch[20];
- struct Node{bool fl;double k,b;}t[MAX<<2];
- void Modify(int now,int l,int r,double K,double B)
- {
- if(!t[now].fl){t[now].fl=true,t[now].k=K;t[now].b=B;return;}
- int mid=(l+r)>>1;
- double l1=l*K+B,r1=r*K+B;
- double l2=l*t[now].k+t[now].b,r2=r*t[now].k+t[now].b;
- if(l1<=l2&&r1<=r2)return;
- if(l1>l2&&r1>r2){t[now].k=K;t[now].b=B;return;}
- double x=(B-t[now].b)/(t[now].k-K);
- if(l1>l2)
- {
- if(x>mid)Modify(rson,mid+1,r,t[now].k,t[now].b),t[now].k=K,t[now].b=B;
- else Modify(lson,l,mid,K,B);
- }
- else
- {
- if(x>mid)Modify(rson,mid+1,r,K,B);
- else Modify(lson,l,mid,t[now].k,t[now].b),t[now].k=K,t[now].b=B;
- }
- }
- double Query(int now,int l,int r,int x)
- {
- if(l==r)return t[now].k*x+t[now].b;
- int mid=(l+r)>>1;double ret=t[now].k*x+t[now].b;
- if(x<=mid)ret=max(ret,Query(lson,l,mid,x));
- else ret=max(ret,Query(rson,mid+1,r,x));
- return ret;
- }
- int main()
- {
- scanf("%d",&Q);
- while(Q--)
- {
- scanf("%s",ch);
- if(ch[0]=='P')
- {
- double K,B;scanf("%lf%lf",&B,&K);
- Modify(1,1,n,K,B-K);
- }
- else
- {
- int x;scanf("%d",&x);
- double ans=Query(1,1,n,x);
- printf("%lld\n",(long long)(ans/100));
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2992832.html