BZOJ_3165_[Heoi2013]Segment_线段树

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)和((x
1+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。

插入时找到线段树上对应log个完全包含的结点。

对于当前结点，如果完全更优或原来没有线段，就插入并返回，如果比当前完全更差也返回，否则向下递归。

查询时查一个点查到底即可。

插入复杂度：每次插入log个区间，递归过程相当于向下二分，于是复杂度O(lognlogn)

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 40050

#define M 39989

#define ls p<<1

#define rs p<<1|1

typedef double f2;

int n,ans,is[N<<2],xx[N<<2],yy[N<<2];

f2 Y,K[N<<2],lv[N<<2],rv[N<<2];

int id;

void insert(int l,int r,int a,int b,f2 k,int y,int p) {

    int mid=(l+r)>>1;

    if(a<=l&&b>=r) {

        f2 lw=y+(l-a)*k,rw=y+(r-a)*k;

        if(!is[p]||(lw>lv[p]&&rw>rv[p])) {

            is[p]=id; lv[p]=lw; rv[p]=rw;

        }else if(lw>lv[p]||rw>rv[p]) {

            insert(l,mid,a,b,k,y,ls);

            insert(mid+1,r,a,b,k,y,rs);

        }

        return ;

    }else {

        if(a<=mid) insert(l,mid,a,b,k,y,ls);

        if(b>mid) insert(mid+1,r,a,b,k,y,rs);

    }

}

void query(int l,int r,int k,int p) {

    if(l==r) {

        if(is[p]&&(lv[p]>Y||(lv[p]==Y&&ans>is[p]))) Y=lv[p],ans=is[p];

        return ;

    }

    if(is[p]) {

        f2 now=lv[p]+1.0*(rv[p]-lv[p])/(r-l)*(k-l);

        if(now>Y||(now==Y&&ans>is[p])) Y=now,ans=is[p];

    }

    int mid=(l+r)>>1;

    if(k<=mid) query(l,mid,k,ls);

    else query(mid+1,r,k,rs);

}

int main() {

    scanf("%d",&n);

    int opt,x_1,y_1,x_2,y_2,i;

    for(i=1;i<=n;i++) {

        scanf("%d%d",&opt,&x_1);

        x_1=(x_1+ans-1)%M+1;

        if(opt==0) {

            Y=-1e15; ans=0;

            query(1,M,x_1,1);

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

        }else {

            id++;

            scanf("%d%d%d",&y_1,&x_2,&y_2);

            y_1=(y_1+ans-1)%1000000000+1;

            x_2=(x_2+ans-1)%M+1;

            y_2=(y_2+ans-1)%1000000000+1;

            if(x_1>x_2) swap(x_1,x_2),swap(y_1,y_2);

            f2 k; int y;

            if(x_1==x_2) k=0,y=max(y_1,y_2);

            else k=1.0*(y_2-y_1)/(x_2-x_1),y=y_1;

            insert(1,M,x_1,x_2,k,y,1);

            // printf("%d %d %d %d\n",x_1,y_1,x_2,y_2);

        }

    }

}

秒客网