nyoj 2361 流星雨（线段树）

2361: 流星雨

题目链接：流星雨

思路：
新加入的一条直线可能会影响若干区间，即区间[a,b]的答案可能由”折线”组成

因此，我们考虑永久化标记，即对于一段区间我们始终用这条直线来标记，除非出现严格更优的直线，否则不删除此直线（新直线下传）

最后答案即为 X 在线段树中对应的叶子到根路径上所有的点答案取max

代码：

#include<bits/stdc++.h>
using namespace std;#define ll rt<<1
#define rr rt<<1|1
#define lson ll,le,mid
#define rson rr,mid+1,riconst int N=5e4;
const int maxn=N+10;
double tagb[maxn<<2],tagk[maxn<<2],ans;double Intersect(double k1,double b1,double k2,double b2)//求交点
{return (b2-b1)/(k1-k2);
}void Update(int rt,int le,int ri,double K,double B)
{if(!tagk[rt])tagk[rt]=K,tagb[rt]=B;else{double s1=tagk[rt]*le+tagb[rt],s2=K*le+B,d1=tagk[rt]*ri+tagb[rt],d2=K*ri+B;if(s2<=s1&&d2<=d1)return ;else if(s2>=s1&&d2>=d1)tagk[rt]=K,tagb[rt]=B;else{int mid=le+ri>>1;double x=Intersect(tagk[rt],tagb[rt],K,B);if(s2>s1){if(x<=mid)Update(lson,K,B);//K和B对左儿子部分区间有影响else//K和B覆盖的更多，因此将tagk和tagb置换，并更新原先的tagk和tagb对右儿子部分区间的影响Update(rson,tagk[rt],tagb[rt]),tagk[rt]=K,tagb[rt]=B;}else if(d2>d1)//同理{if(x<=mid)Update(lson,tagk[rt],tagb[rt]),tagk[rt]=K,tagb[rt]=B;elseUpdate(rson,K,B);}}}
}void Query(int rt,int le,int ri,int x)
{if(tagk[rt])ans=max(ans,tagk[rt]*x+tagb[rt]);if(le==ri)return ;int mid=le+ri>>1;if(x<=mid)return Query(lson,x);elsereturn Query(rson,x);
}int main()
{int op,x,n;double y,k;scanf("%d",&n);while(n--){scanf("%d",&op);if(op==1){scanf("%lf%lf",&y,&k);Update(1,1,N,k,y-k);}else{scanf("%d",&x);ans=0;Query(1,1,N,x);printf("%d\n",(int)floor(ans/100.0));}}return 0;
}