1987. Nested Segments
Time limit: 1.0 secondMemory limit: 64 MB
You are givennsegments on a straight line. For each pair of segments it is known that they either have no common points or all points of one segment belong to the second segment.
Thenmqueries follow. 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 integernthat is the number of segments (1 ≤n≤ 105).i’th of the nextnlines contains integersaiandbithat are the coordinates of endpoints of thei’th segment (1 ≤ai<bi≤ 109). The segments are ordered by non-decreasingai, and whenai=ajthey are ordered by decreasing length. All segments are distinct. The next line contains an integermthat is the number of queries (1 ≤m≤ 105).j’th of the nextmlines contains an integercjthat is the coordinate of the point (1 ≤cj≤ 109). Thequeries are ordered by non-decreasingcj.
Output
For each query output the number of the corresponding segment on a single line. If the point does not belong to any segment, output “-1”. The segments are numbered from 1 tonin order they are given in the input.
Sample
inputoutput
32 102 35 7111234567891011-1221333111-1
题意：
有n个段，编号1-n，每个段占据着a-b。 m个查询，查询c处所在的段中，长度最短的是几号段。如果没有段占据，输出-1。
首先把所有数字存在数组里，去离散化。然后把id按段的长度从长到短更新到树中。然后就查询固定的点在树中的ID的就行了。
#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1#define LL intconst int maxn = 811111; LL ID[maxn<<2];//记录该点属于哪一段void PushUp(int rt) {if(ID[rt<<1] == ID[rt<<1|1])ID[rt]=ID[rt<<1];else ID[rt] = -1;}void PushDown(int rt,int m) {if(ID[rt]!=-1){ID[rt<<1] = ID[rt];ID[rt<<1|1] = ID[rt];}}void build(int l,int r,int rt) { if (l == r) {ID[rt]=-1;return ;}int m = (l + r) >> 1;build(lson);build(rson);PushUp(rt);}void update(int L,int R,int c,int l,int r,int rt) {if (L <= l && r <= R) { ID[rt] = c; return ;}PushDown(rt , r – l + 1);int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (m < R) update(L , R , c , rson);PushUp(rt);}LL query(int L,int R,int l,int r,int rt) {if (L <= l && r <= R) {return ID[rt];}PushDown(rt , r – l + 1);int m = (l + r) >> 1;LL ret = 0;if (L <= m) ret += query(L , R , lson);if (m < R) ret += query(L , R , rson);return ret;}map<int ,int >my;struct bian{int l,r,len;int id;};int num[800010];//用来记录输入的所有的数 用于去离散化bian edge[100010];int qus[100010];//记录询问int cmp(bian a,bian b){return a.len<b.len;}int arr[800010];int main(){int i,a,b;int t,cas=1;int n;int ji;while(scanf("%d",&n)!=EOF){ my.clear();ji=0;for(i=0;i<n;i++){scanf("%d%d",&a,&b);edge[i].l=a;edge[i].r=b;edge[i].len=b-a;edge[i].id=i+1;num[ji++]=a;num[ji++]=b;}int m;scanf("%d",&m);for(i=0;i<m;i++){scanf("%d",&qus[i]);num[ji++]=qus[i];}sort(edge,edge+n,cmp);sort(num,num+ji);int ji2=1;for(i=1;i<ji;i++){if(num[i]!=num[i-1])num[ji2++]=num[i];}ji=ji2;for(i=0;i<ji;i++)my[num[i]]=i+1;build(1,ji,1); for(i=n-1;i>=0;i–)//边长从大到小排序，， 所以从后往前，边长短的会覆盖掉{int l=my[edge[i].l];int r=my[edge[i].r];update(l,r,edge[i].id,1,ji,1);}for(i=0;i<m;i++)printf("%d\n",query(my[qus[i]],my[qus[i]],1,ji,1)); }return 0;}
每一天都是一个阶梯，是向既定目标迈进的新的一步。
