#6034. 「雅礼集训 2017 Day2」线段游戏 李超树

时间：2022-08-04 21:52:15

#6034. 「雅礼集训 2017 Day2」线段游戏

内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：Special Judge
上传者： 匿名

题目描述

给出若干条线段，用 (x1,y2),(x2,y2) (x_1, y_2), (x_2, y_2)(x​1​​,y​2​​),(x​2​​,y​2​​) 表示其两端点坐标，现在要求支持两种操作：

  • 0 x1 y1 x2 y2 表示加入一条新的线段 (x1,y2),(x2,y2) (x_1, y_2), (x_2, y_2)(x​1​​,y​2​​),(x​2​​,y​2​​)；
  • 1 x0 询问所有线段中，x xx 坐标在 x0 x_0x​0​​ 处的最高点的 y yy 坐标是什么，如果对应位置没有线段，则输出 0 00。

输入格式

第一行两个正整数 n nn、m mm 为初始的线段个数和操作个数。
接下来 n nn 行，每行四个整数，表示一条线段。
接下来 m mm 行，每行为一个操作 0 x1 y1 x2 y2 或 1 x0。

输出格式

对于每一个询问操作，输出一行，为一个实数，当你的答案与标准答案误差不超过 10−2 10 ^ {-2}10​−2​​ 时，则视为正确。

样例

样例输入

3 4

0 -1 4 1

4 2 7 2

7 1 8 2

1 4

1 3

0 3 3 6 3

1 3

样例输出

2

0.5

3

对于线段树的每个节点，维护每个节点使得mid的值最大。
对于不优的答案下传。查询时与标记永久化的查询类似。
其实就是李超树。
 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #define maxn 100005

 using namespace std;

 inline int read() {

     int x=,f=;char ch=getchar();

     for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-;

     for(;isdigit(ch);ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 struct seg {double k,b;seg(){b=-;}}t[maxn*];

 inline double cal(seg now,int x) {return now.k*x+now.b;}

 inline void work(int l,int r,int o,seg x) {

     if(cal(t[o],l)>=cal(x,l)&&cal(t[o],r)>=cal(x,r)) {return;}

     if(cal(t[o],l)<cal(x,l)&&cal(t[o],r)<cal(x,r)) {t[o]=x;return;}

     int mid=(l+r)>>,ls=o<<,rs=ls+;

     if(cal(t[o],l)>=cal(x,l)&&cal(t[o],mid)<cal(x,mid)) {

         seg tmp=t[o];t[o]=x;

         work(l,mid,ls,tmp);

         return;

     }

     if(cal(t[o],l)>=cal(x,l)&&cal(t[o],mid)>cal(x,mid)) {

         if(l!=r) work(mid+,r,rs,x);

         return;

     }

     if(cal(t[o],l)<cal(x,l)&&cal(t[o],mid)<cal(x,mid)) {

         seg tmp=t[o];t[o]=x;

         if(l!=r) work(mid+,r,rs,tmp);

         return;

     }

     if(cal(t[o],l)<cal(x,l)&&cal(t[o],mid)>=cal(x,mid)) {

         if(l!=r) work(l,mid,ls,x);

         return;

     }

 }

 inline void update(int l,int r,int o,int L,int R,seg x) {

 //    cout<<l<<' '<<r<<endl;

     if(L<=l&&R>=r) {work(l,r,o,x);return;}

     int mid=(l+r)>>,ls=o<<,rs=ls+;

     if(L<=mid) update(l,mid,ls,L,R,x);

     if(R>mid) update(mid+,r,rs,L,R,x);

 }

 double ans;

 inline double query(int l,int r,int o,int x) {

     if(l==r) return cal(t[o],l);

     int mid=(l+r)>>,ls=o<<,rs=ls+;

     if(x<=mid) return ans=max(ans,max(cal(t[o],x),query(l,mid,ls,x)));

     else return ans=max(ans,max(cal(t[o],x),query(mid+,r,rs,x)));

 }

 int n,m;

 int main() {

     n=read(),m=read();

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

         int x1=read(),y1=read(),x2=read(),y2=read();

         if(x1>x2) {swap(x1,x2);swap(y1,y2);}

         if(x2<||x1>) continue;

         seg x;

         if(x1==x2) x.k=,x.b=max(y1,y2);

         else {

             x.k=(double)(y2-y1)/(double)(x2-x1);

             x.b=y1-x.k*x1;

         }

         update(,,,max(,x1),min(,x2),x);

     }

     while(m--) {

         int tp=read();

         if(tp==) {

             int x1=read(),y1=read(),x2=read(),y2=read();

             if(x1>x2) {swap(x1,x2);swap(y1,y2);}

             if(x2<||x1>) continue;

             seg x;

             if(x1==x2) x.k=,x.b=max(y1,y2);

             else {

                 x.k=(double)(y2-y1)/(double)(x2-x1);

                 x.b=y1-x.k*x1;

             }

             update(,,,max(,x1),min(,x2),x);

         }

         else {

             int x=read();ans=-;

             query(,,,x);

             printf("%.3lf\n",ans==-?:ans);

         }

     }

 }
 

相关文章