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

#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的值最大。对于不优的答案下传。查询时与标记永久化的查询类似。其实就是李超树。

1 #include

2 #include

3 #include

4 #include

5 #include

6 #include

7 #define maxn 100005

8 using namespace std;

9 inline int read() {

10 int x=0,f=1;char ch=getchar();

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

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

13 return x*f;

14 }

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

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

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

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

19 if(cal(t[o],l)

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

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

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

23 work(l,mid,ls,tmp);

24 return;

25 }

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

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

28 return;

29 }

30 if(cal(t[o],l)

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

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

33 return;

34 }

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

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

37 return;

38 }

39 }

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

41 // cout<

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

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

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

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

46 }

47 double ans;

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

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

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

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

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

53 }

54 int n,m;

55 int main() {

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

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

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

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

60 if(x2<1||x1>100000) continue;

61 seg x;

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

63 else {

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

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

66 }

67 update(1,100000,1,max(1,x1),min(100000,x2),x);

68 }

69 while(m--) {

70 int tp=read();

71 if(tp==0) {

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

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

74 if(x2<1||x1>100000) continue;

75 seg x;

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

77 else {

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

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

80 }

81 update(1,100000,1,max(1,x1),min(100000,x2),x);

82 }

83 else {

84 int x=read();ans=-10000000000000000;

85 query(1,100000,1,x);

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

87 }

88 }

89 }

View Code

O(∩_∩)O~ (*^__^*) 嘻嘻…… O(∩_∩)O哈哈~