欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2023-12-31 13:07:28
...

题目描述:

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

题目分析:

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

Code:

#include<bits/stdc++.h>
#define maxn 200005
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
using namespace std;
const int N = 1e5;
const double inf = 1e9;
int n,m;
struct node{
    int x0,y0,x1,y1;double k;
    node input(){
        scanf("%d%d%d%d",&x0,&y0,&x1,&y1),k=x0==x1?inf:(y1-y0)*1.0/(x1-x0);
        if(x0>x1) swap(x0,x1),swap(y0,y1);
        return *this;
    }
    double calc(int x){return k==inf?max(y0,y1):y0+k*(x-x0);}
    bool empty(){return !x0&&!x1&&!k;}
}t[maxn<<2];
void solve(int i,int l,int r,node p){
    if(t[i].empty()) {t[i]=p;return;}
    int mid=(l+r)>>1;
    if(t[i].calc(mid)<p.calc(mid)) swap(t[i],p);
    if(l==r) return;
    if(t[i].k>p.k) solve(i<<1,l,mid,p);
    else solve(i<<1|1,mid+1,r,p);
}
void insert(int i,int l,int r,node p){
    if(p.x1<l||r<p.x0) return;
    if(p.x0<=l&&r<=p.x1) {solve(i,l,r,p);return;}
    int mid=(l+r)>>1;
    insert(i<<1,l,mid,p),insert(i<<1|1,mid+1,r,p);
}
double query(int i,int l,int r,int x){
    double ret=t[i].empty()?-inf:t[i].calc(x);
    if(l==r) return ret;
    int mid=(l+r)>>1;
    if(x<=mid) return max(ret,query(i<<1,l,mid,x));
    else return max(ret,query(i<<1|1,mid+1,r,x));
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) insert(1,0,N,node().input());
    int op,x;double ans;
    while(m--){
        scanf("%d",&op);
        if(!op) insert(1,0,N,node().input());
        else scanf("%d",&x),printf("%.3f\n",(ans=query(1,0,N,x))>-inf?ans:0);
    }
}
相关标签: 李超线段树

上一篇:

下一篇: