ural 1987.Nested Segments【離散化＋欲張り＋線分樹】

1987.Nested Segments
Time limit:1.0 second
Memory limit:64 MB
You are given 
n segments on a stright line.For each pair of segments it is known that they eigther haveのcommon points or all points of one segment belong to the second segment.
The n 
m queries follows.Each query represents a point on the line.For each query,your task is to find the segment of the minimum length,to which this point belongs.
Input
The first line contains an integer 
n that is the number of segments(1≦ 
n ≦10
5) 
i’th of the next 
n LINE contains integers 
a.
i and 
b
i that are the coordination of endpoints of the 
i’th segment(1≦ 
a.
i b
i ≦10
9)The segments ared by non-decreasung 
a.
i,and when 
a.
i = 
a.
j they are orded by decrease length.All segments are distinct.The next line contains an integer 
m that is the number of queries(1≦ 
m ≦10
5) 
j’th of the next 
m ラインcontains an integer 
c
j that is the coordinate of the point(1≦ 
c
j ≦10
9).The queries are orded by non-decreasung 
c
j.
Output
For each query output the number of the cores ponding segment on a single line.If the point does not belong to any segment,output「-1」.The segments are numbend from 1 to 
n in order they are given in the input.
Sample
input
out put

3
2 10
2 3
5 7
11
1
2
3
4
5
6
7
8
9
10
11

-1
2
2
1
3
3
3
1
1
1
-1

Problem Author: Mikhail Rubinchik、idea by Nikita Pervukahin

/*
      ：  n    m   ,                     ,
                  -1
      ：   +  +   
      ：         1e9  ,         ,  n    1e5, 
                    ,              -1,      
                   ,                ,      
                    
*/

#include
#include
#include
#include
#include
using namespace std;
#define int_inf ((1<<31)-1)
#define ll_inf ((1ll<<63)-1)

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;

const int maxn=110000*4*4;
using namespace std;
int n,Q;
int lazy[maxn<<2];
int sum[maxn<<2];
void PushUp(int rt){
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void PushDown(int rt,int m){
	if(lazy[rt]){
		lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
		sum[rt<<1]=(m-(m>>1))*lazy[rt];
		sum[rt<<1|1]=((m>>1))*lazy[rt];
		lazy[rt]=0;
	}
}

void update(int L,int R,int c,int l,int r,int rt){
	if(L<=l && r<=R){
		lazy[rt]=c;
		sum[rt]=c*(r-l+1);
        return ;
	}
	PushDown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m) update(L,R,c,rson);
    PushUp(rt);
}

int query(int L,int R,int l,int r,int rt){
	if(L<=l &&r<=R){
		return sum[rt];
	}
	PushDown(rt,r-l+1);
	int m=(r+l)>>1;
	int ret=0;
	if(L<=m) ret+=query(L,R,lson);
	if(m(e2.b -e2.a );
}
int sz;
int get(int x){
    int l=1,r=sz;
    while(r>=l){
        int mid=(l+r)>>1;
        if(bit[mid]>x) r=mid-1;
        else if(bit[mid]