bzoj1568 Blue Mary

题意：P:加入一条一次函数。Q：询问x位置的最大函数值。

标程：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=200005;
 4 int q,x,n; 
 5 double Tk[N],Tb[N],b,k,ans;
 6 char s[10]; 
 7 void add(int x,int l,int r,double b,double k)
 8 {
 9     if (!Tk[x]&&!Tb[x]) {Tk[x]=k;Tb[x]=b;return;}
10     double fl1=Tk[x]*l+Tb[x],fl2=k*l+b;
11     double fr1=Tk[x]*r+Tb[x],fr2=k*r+b;
12     if (fl1>=fl2&&fr1>=fr2) return;
13     if (fl1<fl2&&fr1<fr2) {Tk[x]=k;Tb[x]=b;return;}
14     double dot=(double)(Tb[x]-b)/(k-Tk[x]);int mid=(l+r)>>1;
15     if (k<Tk[x])
16     {
17         if (dot<=mid) add(x<<1,l,mid,b,k);
18         else add(x<<1|1,mid+1,r,Tb[x],Tk[x]),Tk[x]=k,Tb[x]=b;
19     }else
20     {
21         if (dot<=mid) add(x<<1,l,mid,Tb[x],Tk[x]),Tk[x]=k,Tb[x]=b;
22         else add(x<<1|1,mid+1,r,b,k);
23     }
24 }
25 void qry(int k,int l,int r,int x)
26 {
27     ans=max(ans,Tk[k]*x+Tb[k]);
28     if (l==r) return;
29     int mid=(l+r)>>1;
30     if (x<=mid) qry(k<<1,l,mid,x);else qry(k<<1|1,mid+1,r,x);
31 }
32 int main()
33 {
34     int T;scanf("%d",&T);
35     n=50000;//看清范围！ 
36     while (T--)
37     {
38         scanf("%s",s);
39         if (s[0]=='P')
40         {
41             scanf("%lf%lf",&b,&k);
42             add(1,1,n,b-k,k);
43         }else {
44             scanf("%d",&x);ans=0;
45             qry(1,1,n,x);
46             printf("%d
",(int)(ans/100.0));
47         }
48     }
49     return 0;
50 }

题解：李超树

李超树的一个特点是标记永久化。可以求解有关直线、线段、折线的一系列问题。

每个区间[l,r]保存在x=mid时最高的一条直线。

插入：分类讨论斜率的大小关系和当前区间直线和插入直线的交点。

设Tk为当前区间直线的斜率，k为插入直线的斜率。当Tk>k时，如果交点在mid左边，那么处理左区间插入直线，右区间不变；如果交点在mid右边，那么Tk=k，左区间被插入直线完全覆盖，处理右区间原区间直线。Tk<k的情况同理。

查询：路径上直线的最大值。

时间复杂度O(nlogn)。