Description

要求在平面直角坐标系下维护两个操作：

1. 在平面上加入一条线段。记第i条被插入的线段的标号为i。

2. 给定一个数k，询问与直线x=k相交的线段中，交点最靠上的线段的编号。

Input

第一行一个整数n，表示共n个操作。

接下来n行，每行第一个数为0或1。

若该数为0，则后面跟着一个正整数k，表示询问与直线 x=((k+lastans–1)相交的线段中交点（包括在端点相交的情形）最靠上的线段的编号，其中%表示取余。若某条线段为直线的一部分，则视作直线与线段交于该线段y坐标最大处。若有多条线段符合要求，输出编号最小的线段的编号。

若该数为1，则后面跟着四个正整数x0,y0,x1,y1，表示插入一条两个端点为 ((x0+lastans−1)%39989+1,(y0+lastans−1)%109+1) 和 ((x1+lastans−1)%39989+1,(y1+lastans−1)%109+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≤105 , 1≤k,x0,x1≤39989，1≤y0≤y1≤109。

Source

思路

这道题显然可以用线段树维护。

怎么维护？神奇的线段树标记永久化。

线段树上的节点存这个点的“优势线段”，即完全覆盖这个区间的线段中是最多点的最优解的线段，最终统计答案就从根节点向下搜索到叶子节点，经过树上区间的最优解就是这个点的最优解。

举个例子：

（图片出自，虽然我不知道这个网站是谁创的）

在这个图中，红色代表线段树上的寻找的区间，蓝色代表插入，黑色代表原来这个区间的最优线段，橙色代表这个区间的mid。

可以看出，这个区间显然是蓝色线段占优势，而黑色线段在这个线段的右半部分占优势，并且黑色线段在左半部分完全没有存在的必要了。

那么这个点的值就是蓝色线段的编号，而这个点右儿子的值就是黑色线段的编号。

具体过程……看代码吧。

代码

#include 
    
     #include 
     
      const int maxn=100000;const int maxx=39989;const int maxy=1000000000;int lastans,n;struct segment_tree//线段树{  struct line//记录一条线段  {    int l,r;//这个是左端点和右端点的横坐标    double k,b;//这个是线段所处的直线y=kx+b中的k和b值    double f(int x)//这个是当横坐标为x时纵坐标的值    {      return k*x+b;    }  };  line li[maxn+10];  int val[(maxn<<2)+10],totl,qans;//totl是线段总数，qans是询问的答案  double topv;//topv是询问的最优点的纵坐标  int query(int now,int left,int right,int pos)  //查询left到right区间内是否右pos的最优值  {    if((pos
      
       right))//如果要找到不在这个区间就退出      {        return 0;      }    if(val[now])//如果这个区间有完全被线段覆盖      {        double ff=li[val[now]].f(pos);        //ff是这个区间优势线段在pos这个横坐标的纵坐标值        if((topv
       
        
         >1;//递归寻找左右儿子    query(now<<1,left,mid,pos);    query(now<<1|1,mid+1,right,pos);    return 0;  }  int insert(int now,int left,int right,int insv)  //这个是插入一条编号为insv的线段  {    if((li[insv].l>right)||(li[insv].r
         
          0; int uor=(li[insv].f(right)-li[val[now]].f(right))>0; //uol是在区间左端点时插入的线段的纵坐标是否大于原线段的 //uor是在区间右端点时插入的线段的横坐标是否大于原线段的 if((!val[now])||(uol&&uor)) //如果这个区间还没有值，或者插入线段完全高于原线段，就直接赋值 { val[now]=insv; } else if(uol^uor) //如果两线段在这个区间有交点，就需要分情况讨论 { int mid=(left+right)>>1; double c=(li[insv].b-li[val[now]].b)/(li[val[now]].k-li[insv].k); if((c<=mid)&&uol) //原线段完全覆盖右区间，在左区间与插入线段分割 { insert(now<<1,left,mid,insv); //显然只在左侧插入要插入的线段就好了 } else if((c<=mid)&&uor) //插入线段完全覆盖右区间，在左区间与原线段分割 { insert(now<<1,left,mid,val[now]); val[now]=insv; } else if((c>mid)&&uol) //插入线段完全覆盖左区间，在右区间与原线段分割 { insert(now<<1|1,mid+1,right,val[now]); val[now]=insv; } else if((c>mid)&&uor) //原线段完全覆盖左区间，在有区间与插入线段分割 { insert(now<<1|1,mid+1,right,insv); } } } else//如果这个区间一半被覆盖，一半没有 { //这个区间不讨论，分到下面区间讨论 int mid=(left+right)>>1; insert(now<<1,left,mid,insv); insert(now<<1|1,mid+1,right,insv); } return 0; } int ins(int xa,int ya,int xb,int yb) //插入一条起点坐标为(xa,ya)，终点坐标为(xb,yb)的线段 { ++totl;//记录这一条线段，赋编号 li[totl].l=std::min(xa,xb);//左侧的横坐标 li[totl].r=std::max(xa,xb);//右侧的横坐标 if(xa!=xb)//如果有斜率 { li[totl].k=(double)(yb-ya)/(xb-xa);//计算斜率 li[totl].b=ya-li[totl].k*xa;//计算截距 } else { li[totl].k=0; li[totl].b=std::max(ya,yb); //没有斜率这样处理，因为寻找时f(x)=b=max(ya,yb) } insert(1,1,maxx,totl);//在线段树中插入 return 0; } int ask(int x) { qans=0;//给qans和topv赋初值 topv=-maxy; query(1,1,maxx,x);//在线段树中查找 return qans; }};segment_tree st;int main(){ scanf("%d",&n); while(n--) { int kind,a,b,c,d; scanf("%d",&kind);//kind代表询问的种类 if(kind) { scanf("%d%d%d%d",&a,&b,&c,&d); st.ins((a+lastans-1)%maxx+1,(b+lastans-1)%maxy+1,(c+lastans-1)%maxx+1,(d+lastans-1)%maxy+1); //计算出要求插入的值 } else { scanf("%d",&a); lastans=st.ask((a+lastans-1)%maxx+1); //计算出要求询问的值，并更新lastans printf("%d\n",lastans); } } return 0;}