3165: [Heoi2013]Segment

Time Limit: 40 Sec  Memory Limit: 256 MB

Submit: 368  Solved: 148

[][][]

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {
   if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}int N,M,cnt,lans;struct LineNode{    double k,b; int id;    LineNode(int x0=0,int y0=0,int x1=0,int y1=0,int ID=0)        {            id=ID;            if (x0==x1) k=0,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 1;    return A.getf(x)!=B.getf(x)?A.getf(x)
          
           
            >1; LineNode tmp; if (x<=mid) tmp=Query(now<<1,l,mid,x); else tmp=Query(now<<1|1,mid+1,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)>>1; double X=(tree[now].b-x.b)/(x.k-tree[now].k); if (X
            
             r) return; if (X<=mid) insert(now<<1,l,mid,tree[now]),tree[now]=x; else insert(now<<1|1,mid+1,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)>>1; if (L<=mid) Insert(now<<1,l,mid,L,R,x); if (R>mid) Insert(now<<1|1,mid+1,r,L,R,x);}#define p1 39989#define p2 1000000000int main(){ M=read(); N=50000; while (M--) { int opt=read(); if (opt==0) { int x=read(); x=(x+lans-1)%p1+1; lans=Query(1,1,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==1) { int x0=read(),y0=read(),x1=read(),y1=read(); x0=(x0+lans-1)%p1+1;y0=(y0+lans-1)%p2+1;x1=(x1+lans-1)%p1+1;y1=(y1+lans-1)%p2+1; if (x0>x1) swap(x0,x1),swap(y0,y1); // printf("%d %d %d %d\n",x0,y0,x1,y1); Insert(1,1,N,x0,x1,LineNode(x0,y0,x1,y1,++cnt)); } } return 0;}