一题离散化+线段树
比赛的时候往set方向上写了，但是tle看到网上有人说set也能做。看来又是写cuo了。
队友说过线段树+离散化。但是第二句话就说“太麻烦了，应该不是这样”。。。。其实还是蛮简单的。
看了别人的博客，知道了stl还有lower_bound（）这种东西。。。以后不用手敲二分了。
-----------------------------------------------------------
先说下离散化。与队友共勉。
就这道题而言。数据范围是1e9但是最多只有3*1e5个数字。
离散化的工作就是：
本来线段树表示的是 数字固有大小之间的关系。比如1-5之间有5个数。而离散化之后则表示了数字大小之间的关系（注意，没有了固有）
举个例子 有5个数 10 69 129 4444 1000000 . 一般的线段树需要开辟 1e6*4的空间来存储。而离散化以后。只需要开辟5*4的空间了。
内容就是他们之间的大小关系。 即第一个小的数是 10 ， 第二个小的是 69 第。。。。。第5个小的数是1000000.
说的再简单点，那就看代码的注释了：
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
using namespace std;
const int MAX = 1e5+10;
int id[MAX*3];
int top;
struct segment{
int L , R ;
}S[MAX];
int cnt[(MAX*3)<<2] , q[MAX];
void pushDown(int id){
if( cnt[id<<1] == -1 ) cnt[id<<1] = cnt[id];
if( cnt[id<<1|1] == -1 ) cnt[id<<1|1] = cnt[id];
}
void upData( int L , int R , int l , int r , int id , int ret ){
if( L <= l && r <= R ){
cnt[id] = ret;return;
}
int m = (l+r)>>1;
pushDown(id);//向下更新的操作，就是懒惰标记Lazy
if( L <= m ) upData(L,R,l,m,id<<1,ret);
if( R > m ) upData(L,R,m+1,r,id<<1|1,ret);
}
int query( int x , int l , int r , int id ){
if( l == r && x == l ){
return cnt[id];
}
int m = (l+r)>>1;
pushDown(id);
if( x <= m ) return query(x,l,m,id<<1);
else return query(x,m+1,r,id<<1|1);
}
int main(){
int n;while(~scanf("%d" , &n)){
top = 0;
for( int i = 0 ; i < n ; ++ i ){
scanf("%d%d" , &S[i].L , &S[i].R );
id[ top++ ] = S[i].L;//把所有可能的数字都存入数组id
id[ top++ ] = S[i].R;//把所有可能的数字都存入数组id
}
int m; scanf("%d",&m);
for( int i = 0 ; i <m ; ++ i ){
scanf("%d" , &q[i]);
id[ top++ ] = q[i];//把所有可能的数字都存入数组id
}
sort(id,id+top);//对id进行排序一遍二分查找第k大的数
memset(cnt,-1,sizeof(cnt));//初始段编号为-1
for( int i = 0 ; i < n ; ++ i ){
int L = std::lower_bound(id,id+top,S[i].L)-id;
//lower_bound 是stl的函数返回的是第一个大于等于k的数的位置，k为第三个参数，前两个参数代表查找范围
int R = std::lower_bound(id,id+top,S[i].R)-id;
upData(L,R,0,top,1,i+1 );//接下来就是线段树的知识，把第L大到第R大的段刷新段编号
}
for( int i = 0 ; i < m; ++ i ){
printf("%d\n",query(lower_bound(id,id+top,q[i])-id,0,top,1));//查询段编号
}
}
return 0;
}