-
By: admin
一、题目
点此看题
二、解法
首先讲一种 标枪 的神奇方法，是错误的但是可以骗到
80
80
80 分，我们在下传标记的时候因为无法合并，就把下层的标记再下传一层，那么就避免了合并（要重视这种乱搞的做法）
正解是李超树（内核就是标记永久化），每个点只维护
m
i
d
mid
mid 处最大的线段，这样每个点的最大值都能被维护，因为这道题有两个重要的特点：
0
<
x
0
<
1
e
5
0 0 如果我们加入了新线段覆盖到了这个区间，由于我们维护的是 m i d mid mid 处最好的线段，我们比较他们两个在 m i d mid mid 处的情况。 如果新线段在 m i d mid mid 处更好，那么旧线段就被踢掉了，但它并不是完全没用的。它最多在 [ l , m i d ] , [ m i d + 1 , r ] [l,mid],[mid+1,r] [l,mid],[mid+1,r] 中的一个区间产生贡献，画图的话你就知道取决于旧线段的斜率，实现中我们只需要比较 l l l 或 r r r 处的点只就可以了。 如果还是旧线段在 m i d mid mid 处更好，那么同样用上述方法处理新线段在下面的贡献。 现在你就知道为什么要取 m i d mid mid 了，因为比较之后可以将区间砍成一半之后下传，虽然每个点维护的性质是有限的，但是这复杂度竟然如此有趣。时间复杂度 O ( n log 2 n ) O(n\log^2n) O(nlog2n) #include #include using namespace std; const int M = 100005; const int up = 100000; #define db double int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=x*10+(c^48);c=getchar();} return x*f; } int n,m; struct node { db x1,y1,x2,y2; node() {x1=-1e6;x2=1e6;y1=y2=-1e7;} void in() { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); if(x1>x2) swap(x1,x2),swap(y1,y2);//nmsl 操 } db ask(int x0) { if(x1==x2) return max(y1,y2); db k=1.0*(y1-y2)/(x1-x2); return y1+k*(x0-x1); } }tr[4*M],tmp; void ins(int i,int l,int r,node x) { if(l>x.x2 || x.x1>r) return ; int mid=(l+r)>>1; if(x.x1<=l && r<=x.x2) { if(x.ask(mid)>tr[i].ask(mid)) { if(tr[i].ask(l)>x.ask(l))//可能对左边产生贡献 ins(i<<1,l,mid,tr[i]); if(tr[i].ask(r)>x.ask(r)) ins(i<<1|1,mid+1,r,tr[i]); tr[i]=x; } else { if(tr[i].ask(l) ins(i<<1,l,mid,x); if(tr[i].ask(r) ins(i<<1|1,mid+1,r,x); } return ; } if(x.x1<=mid) ins(i<<1,l,mid,x); if(x.x2>mid) ins(i<<1|1,mid+1,r,x); } db query(int i,int l,int r,int x) { db t=tr[i].ask(x); if(l==r) return t; int mid=(l+r)>>1; if(mid>=x) return max(query(i<<1,l,mid,x),t); return max(query(i<<1|1,mid+1,r,x),t); } int main() { //freopen("game.in","r",stdin); //freopen("game.out","w",stdout); n=read();m=read(); for(int i=1;i<=n;i++) { tmp.in(); ins(1,1,up,tmp); } while(m--) { int op=read(); if(op==0) { tmp.in(); ins(1,1,up,tmp); } else { int x0=read();db t=query(1,1,up,x0); if(t==-1e7) puts("0"); else printf("%.6lf\n",t); } } }