BZOJ 1568 李超线段树

思路：
李超线段树裸题

//By SiriusRen #include <cmath> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 100050 int n,t;char op[10]; struct Tree{double s,p;}tr[N*8]; void insert(int l,int r,int pos,double s,double p){int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;if(tr[pos].s==0&&tr[pos].p==0){tr[pos].s=s,tr[pos].p=p;return;}double val1=tr[pos].s+(mid-1.0)*tr[pos].p;double val2=s+(mid-1.0)*p;if(l==r){if(val2>val1)tr[pos].s=s,tr[pos].p=p;}else if(tr[pos].p==p)tr[pos].s=max(tr[pos].s,s);else if(tr[pos].p>p){if(val1>=val2)insert(l,mid,lson,s,p);else insert(mid+1,r,rson,tr[pos].s,tr[pos].p),tr[pos].s=s,tr[pos].p=p;}else{if(val1>=val2)insert(mid+1,r,rson,s,p);else insert(l,mid,lson,tr[pos].s,tr[pos].p),tr[pos].s=s,tr[pos].p=p;} } double query(int l,int r,int pos,int x){int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1;double ans=max(0.0,tr[pos].s+(x-1.0)*tr[pos].p);if(l==r)return ans;if(x<=mid)ans=max(ans,query(l,mid,lson,x));else ans=max(ans,query(mid+1,r,rson,x));return ans; } int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",op);if(op[0]=='Q'){scanf("%d",&t);printf("%d\n",((int)query(1,50000,1,t))/100);}else if(op[0]=='P'){double s,p;scanf("%lf%lf",&s,&p);insert(1,50000,1,s,p);}} }

转载于:https://www.cnblogs.com/SiriusRen/p/6532075.html

总结

以上是生活随笔为你收集整理的BZOJ 1568 李超线段树的全部内容，希望文章能够帮你解决所遇到的问题。

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