【BZOJ 3165】【HEOI2013】Segment / 题解

【BZOJ 3165】【HEOI2013】Segment / 题解

BZOJ原题地址

洛谷原题地址

思路

可以用线段树很方便地维护,对于每个区间,如果要加地线段在中点处更优,就替换原有的线段。

对于每条新加入的线段,我们需要用$log(n)$ 的复杂度将它分配到不同的区间内,对于每个区间,又要用$log(n)$的复杂度判断在所有子区间的优劣程度。

所以,插入复杂度是$log^2(n)$的,查询复杂度依然为$log(n)$。

代码实现

使用结构体$Node$存储每条线段的信息。

对于一条编号为$id$的线段,它的左端点是$(l,yl)$,而右端点是$(r,yr)$。判断交点的存在性和位置时,我们使用$Node.k$来获取这条线段的斜率。

在插入时,我们会不断调整新线段的左右端点位置以确保被当前区间覆盖,使用$Node.lm()$ / $Node.rm()$ 实现这个操作。

对于斜率不存在的线段要简单地特殊处理一下,我的插入方法能规避很多特判。

细节见注释。

#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100001
#define mid ((l+r)>>1)
using namespace std;
struct Node{
    int l,r,id;
    double yl,yr;
    Node(int x1=0,int y1=0,int x2=0,int y2=0,int i=0){
        l=x1,r=x2;yl=y1,yr=y2;id=i;
        if (l==r) yl=yr=max(yl,yr);
    }
    double get(int x){return l==r?yl:yl+(k()*(x-l));}
    double k(){return (yr-yl)/(r-l);}
    void lm(int x){yl=get(x);l=x;}
    void rm(int x){yr=get(x);r=x;}
};
bool hei(Node a,Node b,int x){
    return a.get(x)==b.get(x)?a.idb.get(x);
}
struct St{
    Node tree[maxn*4];
    void build(int l,int r,int p){
        tree[p].l=l,tree[p].r=r;
        if (l==r) return;
        build(l,mid,ls);
        build(mid+1,r,rs); 
    }
    Node query(int t,int l,int r,int p){
        if (l==r) return tree[p];Node tem;
        if (t<=mid) tem=query(t,l,mid,ls);
        else tem=query(t,mid+1,r,rs);
        return hei(tem,tree[p],t)?tem:tree[p];
    }
    void update(int l,int r,Node k,int p){
        if (tree[p].l>k.l) k.lm(tree[p].l);
        if (tree[p].r=max(k.yl,k.yr)) return;//如果在当前区间内没有交点就直接return
        if (l==r) return;
        if (tree[p].k()<=k.k()) update(mid+1,r,k,rs);//判断交点的位置
        else update(l,mid,k,ls);
    }
    void insert(int l,int r,Node k,int p){
        if (k.l>r||k.rk.l) k.lm(tree[p].l);
        if (tree[p].r>m;
    while(m--){
        int temp;cin>>temp;
        if (!temp){
            int k;cin>>k;
            k=(k+la-1)%39989+1;
            la=T.query(k,1,n,1).id;
            cout<>x0>>y0>>x1>>y1;
            x0=(x0+la-1)%39989+1;x1=(x1+la-1)%39989+1;
            y0=(y0+la-1)%1e9+1;y1=(y1+la-1)%1e9+1;//注意是1e9,而非题目所述的109
            if (x0>x1) swap(x0,x1),swap(y0,y1);
            Node tem=Node(x0,y0,x1,y1,++Ind);
            T.insert(1,n,tem,1);
        }
    }
}
Show Comments