【题解】[HEOI2013] Segment 李超线段树 —Qiuly

好像最近更博很不积极啊。

先介绍一下李超线段树是什么。

李超线段树用于维护二维平面上的线段，并支持查询 $x=k$ 的轴上或者是一段 $l,r$ 的区间中的线段所在的 $y$ 的最大值/最小值。

插入操作：对于每一个线段树上的点 $x$ ，定 $x$ 的代表区间为 $l,r$ ，那么 $x$ 点所记录的就是 $x=mid$ 轴上的最高/最低的线段。插入线段时，对于当前节点 $x$ ：

• 如果当前需要插入的线段在 $mid$ 轴上大于 $x$ 的最优线段，那么将 $x$ 所记录线段替换为当前线段。
• 接着，如果需要插入的线段在 $l,r$ 位置都低于当前 $x$ 所记录的线段，那么插入的线段显然对 $x$ 的所有子树节点都做不出贡献，$return$ 。
• 然后，如果 $l,r$ 的一头是插入线段更高，另一头是 $x$ 记录的线段更高，那么直接去更新 $x$ 的儿子即可。

询问操作：按照普通的线段树搞即可。

这一题显然就是板子题。

Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=1e5+2;
const int X=39989+2;
const int Y=1e9;

struct Segment {
    int x1,x2,id;
    double y1,y2;
    Segment(int a=0,int b=0,int c=0,int d=0,int i=0) {
        x1=a,x2=b,y1=c,y2=d,id=i;
        if(x1==x2) y1=y2=max(y1,y2);
    }
    double moving(int x) {return x1==x2?y1:y1+(slope()*(x-x1));}
    double slope() {return (y2-y1)/(x2-x1);}
    void moving_l(int x) {y1=moving(x);x1=x;}
    void moving_r(int x) {y2=moving(x);x2=x;}
};
bool Comparison(Segment a,Segment b,int c) {
    return a.moving(c)==b.moving(c)?a.id<b.id:a.moving(c)>b.moving(c);
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

struct Segment_Tree {
    #define mid ((l+r)>>1)
    #define lc (x<<1)
    #define rc (x<<1|1)
    Segment t[N<<2];
    void build(int x,int l,int r) {
        t[x].x1=l,t[x].x2=r;
        if(l==r) return;
        build(lc,l,mid),build(rc,mid+1,r);
    }
    void update(int x,int l,int r,Segment p) {
        if(t[x].x1>p.x1) p.moving_l(t[x].x1);
        if(t[x].x2<p.x2) p.moving_r(t[x].x2);
        if(Comparison(p,t[x],mid)) swap(t[x],p);
        if(min(t[x].y1,t[x].y2)>=max(p.y1,p.y2)) return;
        if(l==r) return;
        if(t[x].slope()<=p.slope()) update(rc,mid+1,r,p);
        else update(lc,l,mid,p);
    }
    void insert(int x,int l,int r,Segment p) {
        if(p.x1>r||l>p.x2) return;
        if(t[x].x1>p.x1) p.moving_l(t[x].x1);
        if(t[x].x2<p.x2) p.moving_r(t[x].x2);
        if(l==p.x1&&r==p.x2) {update(x,l,r,p);return;}
        if(l==r) return;
        insert(lc,l,mid,p),insert(rc,mid+1,r,p);
    }
    Segment query(int x,int l,int r,int pos) {
        if(l==r) return t[x];
        Segment res;
        if(pos<=mid) res=query(lc,l,mid,pos);
        else res=query(rc,mid+1,r,pos);
        return Comparison(res,t[x],pos)?res:t[x];
    }
}T;

int main() {
    // freopen("P4097.in","r",stdin);
    // freopen("P4097.out","w",stdout);
    int lastans=0,cnt=0,n=39989,q;
    IN(q),T.build(1,1,n);
    while(q--) {
        int op;IN(op);
        if(!op) {
            int c;IN(c),c=(c+lastans-1)%n+1;
            printf("%d\n",lastans=T.query(1,1,n,c).id);
        } else {
            int x0,x1,y0,y1;IN(x0),IN(y0),IN(x1),IN(y1);
            x0=(x0+lastans-1)%n+1,x1=(x1+lastans-1)%n+1;
            y0=(y0+lastans-1)%Y+1,y1=(y1+lastans-1)%Y+1;
            if(x0>x1) swap(x0,x1),swap(y0,y1);
            Segment res=Segment(x0,x1,y0,y1,++cnt);
            T.insert(1,1,n,res);
        }
    }
    return 0;
}