suppose that we are given m segments like [[l1,r1],[l2,r2],…[lm,rm]] where 1<=li<=ri<=n and

n=2e5,m=2e5.

suppose q queries are given each of form L1,R1 where 1<=Li<=Ri<=n ,1<=q<=2e5.

can we find in o(1)or o(logn) for each query whether Li,Ri covers atleast one out of m given segments i.e Li<=lj&&Ri>=rj for atleast one j.

if anyone knows about it or has any idea please help

@carre

@ssjgz

@galencolin or anyone who knows about it please help

build array max_ending_before[n] like this:

```
max_ending_before[i] = -1 (for i in [1,n])
for i=1 to m
max_ending_before[Ri] = max(max_ending_before[Ri],Li)
for i=2 to n
max_ending_before[i] = max(max_ending_before[i],max_ending_before[i-1],)
```

Now you can ans each query in O(1) just looking if max_ending_before[Rq]>=Lq

Although @carre solution is much more efficient than mine, I would share an O(log(n)) approach. Sort the coordinates [l_i, r_i] according to l_i first. Then in each query you can find the smallest j(using upper/lower bound) such that L_i \leq l_j. The only thing now left is to check whether there is some k in [j, n] such that r_k \leq R_i. So you just need to store the suffix minimum, that is:

```
suffixmin[i] = min(suffixmin[i+1], r[i])
```

Therefore when you have calculated the index j in the discussion above just check if suffixmin[j] \leq R_i.

One advantage of this solution is that it does not require the constraint 1 \leq l_i \leq r_i \leq n. It works for any lower/upper bounds on the values.

thanks i will make sure sure that i try both the approches as they both are equivalently good