题目链接:?space=1&num=1987
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条线段，每两条线段要么满足没有公共部分，要么包含。给出m个询问，求当前点被覆盖的最小长度的线段编号。
代码一：（先记录左边比询问点小的线段，然后再在这些点中删掉右边还比询问点小的）；
#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>using namespace std;const int maxn = 100017;int tt[maxn];int n, m;struct node{int l, r;int num;} x[maxn];bool cmp(node a, node b){return a.l < b.l;}int cnt = 0, k = 1;int findd(int q){while(q >= x[k].l){tt[++cnt] = k;k++;if(k > n)break;}while(q > x[tt[cnt]].r){cnt–;if(cnt < 1)break;}return x[tt[cnt]].num;}int main(){int ans[maxn];while(~scanf("%d",&n)){memset(ans, 0, sizeof(ans));int ll, rr;int minn = maxn, maxx = -1;for(int i = 1; i <= n; i++){scanf("%d%d",&ll,&rr);if(ll < minn){minn = ll;}if(rr > maxx){maxx = rr;}x[i].l = ll, x[i].r = rr;x[i].num = i;}int t, q[maxn];memset(tt, 0, sizeof(tt));scanf("%d",&m);for(int i = 1; i <= m; i++){scanf("%d",&t);q[i] = t;}for(int i = 1; i <= m; i++){if(q[i] < minn || q[i] > maxx){ans[i] = -1;continue;}ans[i] = findd(q[i]);}for(int i = 1; i <= m; i++){printf("%d\n",ans[i]);}}return 0;}代码二：（正解）：
由于线段不存在部分相交的情况，，因此，直接按照输入顺序覆盖区间就可以了，因为后覆盖的线段更短
来自：
//STATUS:C++_AC_187MS_6805KB#include <functional>#include <algorithm>#include <iostream>//#include <ext/rope>#include <fstream>#include <sstream>#include <iomanip>#include <numeric>#include <cstring>#include <cassert>#include <cstdio>#include <string>#include <vector>#include <bitset>#include <queue>#include <stack>#include <cmath>#include <ctime>#include <list>#include <set>#include <map>using namespace std;//#pragma comment(linker,"/STACK:102400000,102400000")//using namespace __gnu_cxx;//define#define pii pair<int,int>#define mem(a,b) memset(a,b,sizeof(a))#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1#define PI acos(-1.0)//typedeftypedef __int64 LL;typedef unsigned __int64 ULL;//constconst int N=100010;const int INF=0x3f3f3f3f;const int MOD=95041567,STA=8000010;const LL LNF=1LL<<60;const double EPS=1e-8;const double OO=1e15;const int dx[4]={-1,0,1,0};const int dy[4]={0,1,0,-1};const int day[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//Daily Use …inline int sign(double x){return (x>EPS)-(x<-EPS);}template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}template<class T> inline T lcm(T a,T b,T d){return a/d*b;}template<class T> inline T Min(T a,T b){return a<b?a:b;}template<class T> inline T Max(T a,T b){return a>b?a:b;}template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}//Endint c[(N*3)<<2],t[N][2],q[N],id[N*3];int n;void pushdown(int rt){if(c[rt]!=-1)c[rt<<1]=c[rt<<1|1]=c[rt];}void pushup(int rt){if(c[rt<<1]==c[rt<<1|1])c[rt]=c[rt<<1];else c[rt]=-1;}void update(int l,int r,int rt,int L,int R,int val){if(L<=l && r<=R){c[rt]=val;return;}pushdown(rt);int mid=(l+r)>>1;if(L<=mid)update(lson,L,R,val);if(R>mid)update(rson,L,R,val);pushup(rt);}int query(int l,int r,int rt,int w){if(l==r){return c[rt];}pushdown(rt);int mid=(l+r)>>1,ret;if(w<=mid)ret=query(lson,w);else ret=query(rson,w);pushup(rt);return ret;}int main(){ // freopen("in.txt","r",stdin);int i,j,k,L,R,m;while(~scanf("%d",&n)){k=0;for(i=1;i<=n;i++){scanf("%d%d",&t[i][0],&t[i][1]);id[k++]=t[i][0];id[k++]=t[i][1];}scanf("%d",&m);for(i=0;i<m;i++){scanf("%d",&q[i]);id[k++]=q[i];}sort(id,id+k);k=unique(id,id+k)-id;mem(c,-1);for(i=1;i<=n;i++){L=lower_bound(id,id+k,t[i][0])-id+1;R=lower_bound(id,id+k,t[i][1])-id+1;update(1,k,1,L,R,i);}for(i=0;i<m;i++){printf("%d\n",query(1,k,1,lower_bound(id,id+k,q[i])-id+1));}}return 0;}
找寻隐藏在山间的纯净和那“鸟鸣山更幽”的飞鸟。
