正题

题目链接:https://www.luogu.com.cn/problem/P4254

---

题目大意

要求支持操作

插入一条直线。

询问一个纵坐标最高的在直线上的点。

---

解题思路

李超树的模板题，大概就是标记永久化，对于一个位置$mid$，我们看一下它与标记点在$mid$处的关系再决定它的走向。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll L=5e4,N=1e5+10; ll n,cnt,t[N<<4]; double k[N],b[N]; double w(ll x,ll id) {return k[id]*(x-1)+b[id];} void Change(ll x,ll l,ll r,ll id){if(w(l,id)>=w(l,t[x])&&w(r,id)>=w(r,t[x])){t[x]=id;return;}if(w(l,id)<=w(l,t[x])&&w(r,id)<=w(r,t[x]))return;if(l==r)return;ll mid=(l+r)>>1;if(k[id]>k[t[x]]){if(w(mid,id)>=w(mid,t[x]))Change(x*2,l,mid,t[x]),t[x]=id;else Change(x*2+1,mid+1,r,id);}else{if(w(mid,id)>=w(mid,t[x]))Change(x*2+1,mid+1,r,t[x]),t[x]=id;else Change(x*2,l,mid,id);}return; } double Ask(ll x,ll l,ll r,ll pos){if(l==r)return w(t[x],pos);ll mid=(l+r)>>1;if(pos<=mid)return max(Ask(x*2,l,mid,pos),w(pos,t[x]));return max(Ask(x*2+1,mid+1,r,pos),w(pos,t[x])); } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++){char op[10];scanf("%s",op);if(op[0]=='P'){++cnt;scanf("%lf%lf",&b[cnt],&k[cnt]);Change(1,1,L,cnt);}else{ll x;scanf("%lld",&x);printf("%d\n",(int)(Ask(1,1,L,x)/100));}} }

总结

以上是生活随笔为你收集整理的P4254-[JSOI2008]Blue Mary开公司【李超树】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。