3165: [Heoi2013]Segment 线段树 标记永久化

Description

要求在平面直角坐标系下维护两个操作：
1.在平面上加入一条线段。记第i条被插入的线段的标号为i。
2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。

题解：

实现起来还是比较简单的，注意相同时输出编号较小的线段。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int Maxn=100010,Maxk=40000;
const double eps=1e-7;
struct line
{
    bool flag;
    int x0,y0,x1,y1;
    double k,b;
    line(int _x0=0,int _y0=0,int _x1=0,int _y1=0)
    {
        x0=_x0,y0=_y0,x1=_x1,y1=_y1;
        if(abs(x0-x1)>eps)k=(double)(y0-y1)/(x0-x1),flag=true;
        else flag=false;
        b=(double)y0-k*x0;
    }
}L[Maxn];int llen=0;
double get(int x,int p)
{
    if(L[p].flag)return (double)x*L[p].k+L[p].b;
    else return max(L[p].y0,L[p].y1);
}
struct Seg{int l,r,lc,rc,tag;bool empty;}tr[Maxk<<1];
int tot=0;
void build(int l,int r)
{
    int t=++tot;
    tr[t].l=l;tr[t].r=r;tr[t].tag=-1;tr[t].empty=true;
    if(l==r)return;
    int mid=l+r>>1;
    tr[t].lc=tot+1,build(l,mid);
    tr[t].rc=tot+1,build(mid+1,r);
}
int query(int x,int p)
{
    if(tr[x].empty)return 0;
    if(tr[x].l==tr[x].r)return tr[x].tag;
    int mid=tr[x].l+tr[x].r>>1,lc=tr[x].lc,rc=tr[x].rc,re=tr[x].tag,t;
    if(p<=mid)t=query(lc,p);
    else t=query(rc,p);
    if(re==-1)re=t;
    else
    {
        if(t>0&&get(p,t)>get(p,re))re=t;
        else if(t>0&&abs(get(p,t)-get(p,re))<=eps&&t<re)re=t;
    }
    if(re==-1)re=0;
    return re;
}
void work(int x,int l,int r,int p)
{
    if(tr[x].tag==-1)
    {
        tr[x].tag=p;
        tr[x].empty=false;
        return;
    }
    int mid=tr[x].l+tr[x].r>>1,lc=tr[x].lc,rc=tr[x].rc;
    if(get(l,p)<=get(l,tr[x].tag)&&get(r,p)<=get(r,tr[x].tag))return;
    if(get(l,p)>=get(l,tr[x].tag)&&get(r,p)>=get(r,tr[x].tag)&&
    (abs(get(l,p)-get(l,tr[x].tag))>eps&&abs(get(r,p)-get(r,tr[x].tag))>eps)){tr[x].tag=p;return;}
    if(l==r)return;
    int t=tr[x].tag;
    double Y1=get(l,p),Y2=get(r,p),Y3=get(l,t),Y4=get(r,t);
    double X=(L[p].b-L[t].b)/(L[t].k-L[p].k);
    if(X<=mid)
    {
        if(Y1>Y3)
        {
            tr[x].tag=t;
            work(lc,l,mid,p);
        }
        else
        {
            tr[x].tag=p;
            work(lc,l,mid,t);
        }
    }
    else
    {
        if(Y1>Y3)
        {
            tr[x].tag=p;
            work(rc,mid+1,r,t);
        }
        else
        {
            tr[x].tag=t;
            work(rc,mid+1,r,p);
        }
    }
}
void insert(int x,int l,int r,int p)
{
    int mid=tr[x].l+tr[x].r>>1,lc=tr[x].lc,rc=tr[x].rc;
    if(tr[x].l==l&&tr[x].r==r)
    {
        work(x,l,r,p);
        return;
    }
    if(r<=mid)insert(lc,l,r,p);
    else if(l>mid)insert(rc,l,r,p);
    else insert(lc,l,mid,p),insert(rc,mid+1,r,p);
    tr[x].empty=(tr[lc].empty&tr[rc].empty);
}
int n;
int main()
{
    build(1,Maxk);
    int ans=0;
    scanf("%d",&n);
    while(n--)
    {
        int op,k;
        scanf("%d",&op);
        if(!op)
        {
            scanf("%d",&k);
            int x=((k+ans-1)%39989+1);
            ans=query(1,x);
            printf("%d\n",ans);
        }
        else
        {
            int x0,y0,x1,y1;
            scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
            x0=(x0+ans-1)%39989+1,y0=(y0+ans-1)%1000000000+1;
            x1=(x1+ans-1)%39989+1,y1=(y1+ans-1)%1000000000+1;
            if(x0>x1)swap(x0,x1),swap(y0,y1);
            L[++llen]=line(x0,y0,x1,y1);
            insert(1,x0,x1,llen);
        }
    }
}