正題

題目鏈接: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开公司【李超树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。