[bzoj1568]李超线段树模板题(标志永久化)

题意：要求在平面直角坐标系下维护两个操作：

1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。

解题关键：注意标志的作用，注意虽然存的是索引，但是线段树的范围是天数的范围，也就是线段树是依据天数建的树

复杂度：$O(nlogn)$

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int N=;

 double a[N],b[N],ans;

 int tr[N<<];

 bool check(int x,int y,int t){

     return a[x]+b[x]*(t-)>a[y]+b[y]*(t-);

 }

 void update(int rt,int l,int r,int now){

     if(l==r){

         if(check(now,tr[rt],l)) tr[rt]=now;

         return;

     }

     int mid=(l+r)>>;

     if(b[now]>b[tr[rt]]){

         if(check(now, tr[rt], mid)) update(rt<<,l, mid, tr[rt]),tr[rt]=now;//更新的最后一个是tr[rt]?存的是下标，询问时肯定按log的顺序，而此时now的掌控区间已经确定，需要更新tr[rt]的掌控区间

         else update(rt<<|, mid+, r, now);

     }

     else{

         if(check(now,tr[rt],mid)) update(rt<<|, mid+, r, tr[rt]),tr[rt]=now;

         else update(rt<<, l, mid, now);

     }

 }

 void query(int rt,int l,int r,int now){

     ans=max(ans,a[tr[rt]]+b[tr[rt]]*(now-));

     if(l==r) return;

     int mid=(l+r)>>;

     if(now<=mid) query(rt<<, l, mid, now);

     else query(rt<<|, mid+, r, now);

 }

 int main(){

     int n,m=,c;

     char s[];

     scanf("%d",&n);

     for(int i=;i<n;i++){

         scanf("%s",s);

         if(s[]=='P'){

             m++;

             scanf("%lf%lf",a+m,b+m);

             update(, ,n, m);//线段树中存的是下标，而值需要计算

         }else{

             scanf("%d",&c);

             ans=;

             query(, ,n, c);

             printf("%d\n",(int)ans/);

         }

     }

     return ;

 }

模板2：主要是query函数的两种写法，此写法不需要建全局变量

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 using namespace std;

 typedef long long ll;

 const int N=;

 double a[N],b[N],ans;

 int tr[N<<];

 bool check(int x,int y,int t){

     return a[x]+b[x]*(t-)>a[y]+b[y]*(t-);

 }

 void update(int rt,int l,int r,int now){

     if(l==r){

         if(check(now,tr[rt],l)) tr[rt]=now;

         return;

     }

     int mid=(l+r)>>;

     if(b[now]>b[tr[rt]]){

         if(check(now, tr[rt], mid)) update(rt<<,l, mid, tr[rt]),tr[rt]=now;//更新的最后一个是tr[rt]?存的是下标，询问时肯定按log的顺序，而此时now的掌控区间已经确定，需要更新tr[rt]的掌控区间

         else update(rt<<|, mid+, r, now);

     }

     else{

         if(check(now,tr[rt],mid)) update(rt<<|, mid+, r, tr[rt]),tr[rt]=now;

         else update(rt<<, l, mid, now);

     }

 }

 double query(int rt,int l,int r,int now){

     double ans=max(0.0,a[tr[rt]]+b[tr[rt]]*(now-));

     if(l==r) return ans;

     int mid=(l+r)>>;

     if(now<=mid) ans=max(ans,query(rt<<, l, mid, now));

     else ans=max(ans,query(rt<<|, mid+, r, now));

     return ans;

 }

 int main(){

     int n,m=,c;

     char s[];

     scanf("%d",&n);

     for(int i=;i<n;i++){

         scanf("%s",s);

         if(s[]=='P'){

             m++;

             scanf("%lf%lf",a+m,b+m);

             update(, ,n, m);//线段树中存的是下标，而值需要计算

         }else{

             scanf("%d",&c);

             double ans=query(, ,n, c);

             printf("%d\n",(int)ans/);

         }

     }

     return ;

 }

巴特西

[bzoj1568]李超线段树模板题(标志永久化)

最新文章

热门文章