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

1.在平面上加入一条线段。记第i条被插入的线段的标号为i。  2.给定一个数k,询问与直线 x = k相交的线段中，交点最靠上的线段的编号。  

 

第一行一个整数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。     

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

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

2
0 3

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

题解： 用线段树维护每段位置分别被哪条线段覆盖。

           插入线段的时候如果这条线段对这个区间有贡献，就把它保留在这个区间。

           对于每次查询,从根一直查到底,对中途遇到的线段取最优值即可。

           注意处理斜率不存在的线段。

代码：

        

#include
    
     #include
     
      #include
      
       #include
       
        #define N 100010#define P 39989#define MOD 1000000000#define eps 1e-10using namespace std;int t[N<<2],ansa,n,y,x2,y2,kind,top,a[N],x,lastans;double b[N],ansb;struct use{   double k,b;   int l,r;   double f(int x){return k*x+b;}}line[N];int cross(use a,use b){  return floor((b.b-a.b)/(a.k-b.k));}use cal(int x,int y,int x2,int y2){   use ans;  ans.r=max(x,x2);ans.l=min(x,x2);  if (x2!=x) ans.k=(y2-y)/(double)(x2-x),ans.b=y-ans.k*x;  else ans.k=0.0,ans.b=max(y,y2);  return ans;}int check(double x){  return (x>-eps)-(x
        
         0||(ff==0&&k
         
          0; int fr=check(line[x].f(r)-line[t[k]].f(r))>0; if (fl&&fr) t[k]=x; else if(fl||fr){ int mid=(l+r)>>1; int p=cross(line[x],line[t[k]]); if (p<=mid&&fl) insert(k<<1,l,mid,x); if (p<=mid&&fr) insert(k<<1,l,mid,t[k]),t[k]=x; if (p>mid&&fl) insert(k<<1|1,mid+1,r,t[k]),t[k]=x; if (p>mid&&fr) insert(k<<1|1,mid+1,r,x); } else up(x,l),up(x,r); } return; } int mid=(l+r)>>1; if (line[x].l<=mid) insert(k<<1,l,mid,x); if (line[x].r>mid) insert(k<<1|1,mid+1,r,x);}void query(int k,int l,int r,int x){ if (t[k]){ double tt=line[t[k]].f(x); int ff=check(tt-ansb); if ((ff>0||(ff==0&&ansa
          
           >1; if (x<=mid) query(k<<1,l,mid,x); else query(k<<1|1,mid+1,r,x); }int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&kind); if (kind){ scanf("%d%d%d%d",&x,&y,&x2,&y2); x=(x+lastans-1)%P+1;x2=(x2+lastans-1)%P+1; y=(y+lastans-1)%MOD+1;y2=(y2+lastans-1)%MOD+1; line[++top]=cal(x,y,x2,y2); //cout<
           
            <<' '<
            
             <<' '<
             
              <<' '<
              
               <
               
                0||(ff==0&&a[x]