【BZOJ-3165】Segment 李超线段树（标记永久化）

3165: [Heoi2013]Segment

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 368 Solved: 148
[Submit][Status][Discuss]

Description

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

Input

第一行一个整数n，表示共n 个操作。
接下来n行，每行第一个数为0或1。
若该数为 0，则后面跟着一个正整数 k，表示询问与直线
x = ((k +lastans–1)%39989+1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。
若该数为 1，则后面跟着四个正整数 x0, y0, x 1, y 1，表示插入一条两个端点为
((x0+lastans-1)%39989+1,(y0+lastans-1)%10^9+1)和((x1+lastans-1)%39989+1,(y1+lastans-1)%10^9+1) 的线段。
其中lastans为上一次询问的答案。初始时lastans=0。

Output

对于每个 0操作，输出一行，包含一个正整数，表示交点最靠上的线段的编号。若不存在与直线相交的线段，答案为0。

Sample Input

6
1 8 5 10 8
1 6 7 2 6
0 2
0 9
1 4 7 6 7
0 5

Sample Output

2
0 3

HINT

对于100%的数据，1 ≤ n ≤ 10^5 , 1 ≤ k, x0, x1 ≤ 39989, 1 ≤ y0 ≤ y1 ≤ 10^9。

Source

Solution

李超线段树，和上一个题非常相似

这里只需要计算一下斜率即可...所以认为是双倍经验?

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int N,M,cnt,lans;

struct LineNode

{

    double k,b; int id;

    LineNode(int x0=,int y0=,int x1=,int y1=,int ID=)

        {

            id=ID;

            if (x0==x1) k=,b=max(y0,y1);

            else k=(double)(y0-y1)/(x0-x1),b=(double)y0-k*x0;

        }

    double getf(double x) {return k*x+b;}

};

bool cmp(LineNode A,LineNode B,double x)

{

    if (!A.id) return ;

    return A.getf(x)!=B.getf(x)?A.getf(x)<B.getf(x):A.id<B.id;

}

#define maxn 50010

LineNode tree[maxn<<];

LineNode Query(int now,int l,int r,int x)

{

    if (l==r) return tree[now];

    int mid=(l+r)>>; LineNode tmp;

    if (x<=mid) tmp=Query(now<<,l,mid,x);

    else tmp=Query(now<<|,mid+,r,x);

    return cmp(tree[now],tmp,x)?tmp:tree[now];

}

void insert(int now,int l,int r,LineNode x)

{

    if (!tree[now].id) tree[now]=x;

    if (cmp(tree[now],x,l)) swap(tree[now],x);

    if (l==r || tree[now].k==x.k) return;

    int mid=(l+r)>>; double X=(tree[now].b-x.b)/(x.k-tree[now].k);

    if (X<l || X>r) return;

    if (X<=mid) insert(now<<,l,mid,tree[now]),tree[now]=x;

    else insert(now<<|,mid+,r,x);

}

void Insert(int now,int l,int r,int L,int R,LineNode x)

{

    if (L<=l && R>=r) {insert(now,l,r,x); return;}

    int mid=(l+r)>>;

    if (L<=mid) Insert(now<<,l,mid,L,R,x);

    if (R>mid) Insert(now<<|,mid+,r,L,R,x);

}

#define p1 39989

#define p2 1000000000

int main()

{

    M=read(); N=;

    while (M--)

        {

            int opt=read();

            if (opt==)

                {

                    int x=read(); x=(x+lans-)%p1+; lans=Query(,,N,x).id;

                //    printf("%d %.3lf %.3lf\n",Query(1,1,N,x).id,Query(1,1,N,x).k,Query(1,1,N,x).b);

                    printf("%d\n",lans);

                }

            if (opt==)

                {

                    int x0=read(),y0=read(),x1=read(),y1=read();

                    x0=(x0+lans-)%p1+;y0=(y0+lans-)%p2+;x1=(x1+lans-)%p1+;y1=(y1+lans-)%p2+;

                    if (x0>x1) swap(x0,x1),swap(y0,y1);

                //    printf("%d %d %d %d\n",x0,y0,x1,y1);

                    Insert(,,N,x0,x1,LineNode(x0,y0,x1,y1,++cnt));

                }

        }

    return ;

}

秒客网