题意：要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。 2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。
解题关键：注意标志的作用，注意虽然存的是索引，但是线段树的范围是天数的范围，也就是线段树是依据天数建的树
复杂度：$O(nlogn)$
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long ll; 9 const int N=100004;10 double a[N],b[N],ans;11 int tr[N<<2];12 bool check(int x,int y,int t){13 return a[x]+b[x]*(t-1)>a[y]+b[y]*(t-1);14 }15 16 void update(int rt,int l,int r,int now){17 if(l==r){18 if(check(now,tr[rt],l)) tr[rt]=now;19 return;20 }21 int mid=(l+r)>>1;22 if(b[now]>b[tr[rt]]){23 if(check(now, tr[rt], mid)) update(rt<<1,l, mid, tr[rt]),tr[rt]=now;//更新的最后一个是tr[rt]?存的是下标，询问时肯定按log的顺序，而此时now的掌控区间已经确定，需要更新tr[rt]的掌控区间24 else update(rt<<1|1, mid+1, r, now);25 }26 else{27 if(check(now,tr[rt],mid)) update(rt<<1|1, mid+1, r, tr[rt]),tr[rt]=now;28 else update(rt<<1, l, mid, now);29 }30 }31 32 void query(int rt,int l,int r,int now){33 ans=max(ans,a[tr[rt]]+b[tr[rt]]*(now-1));34 if(l==r) return;35 int mid=(l+r)>>1;36 if(now<=mid) query(rt<<1, l, mid, now);37 else query(rt<<1|1, mid+1, r, now);38 }39 40 int main(){41 int n,m=0,c;42 char s[10];43 scanf("%d",&n);44 for(int i=0;i
模板2：主要是query函数的两种写法，此写法不需要建全局变量
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long ll; 9 const int N=100004;10 double a[N],b[N],ans;11 int tr[N<<2];12 bool check(int x,int y,int t){13 return a[x]+b[x]*(t-1)>a[y]+b[y]*(t-1);14 }15 16 void update(int rt,int l,int r,int now){17 if(l==r){18 if(check(now,tr[rt],l)) tr[rt]=now;19 return;20 }21 int mid=(l+r)>>1;22 if(b[now]>b[tr[rt]]){23 if(check(now, tr[rt], mid)) update(rt<<1,l, mid, tr[rt]),tr[rt]=now;//更新的最后一个是tr[rt]?存的是下标，询问时肯定按log的顺序，而此时now的掌控区间已经确定，需要更新tr[rt]的掌控区间24 else update(rt<<1|1, mid+1, r, now);25 }26 else{27 if(check(now,tr[rt],mid)) update(rt<<1|1, mid+1, r, tr[rt]),tr[rt]=now;28 else update(rt<<1, l, mid, now);29 }30 }31 32 double query(int rt,int l,int r,int now){33 double ans=max(0.0,a[tr[rt]]+b[tr[rt]]*(now-1));34 if(l==r) return ans;35 int mid=(l+r)>>1;36 if(now<=mid) ans=max(ans,query(rt<<1, l, mid, now));37 else ans=max(ans,query(rt<<1|1, mid+1, r, now));38 return ans;39 }40 41 int main(){42 int n,m=0,c;43 char s[10];44 scanf("%d",&n);45 for(int i=0;i