Nested Segments
题面


题目描述
给你n个闭区间，让你判断是否有两个区间之间存在包含关系（解释：如果有两个区间A[a,b] B[c,d]，当a<=c且b>=d时，我们认定A与B存在包含关系）。如果对题意还是不理解的可以看样例与note。
题目分析
这道题一出来，最朴素的解法就是暴力枚举所有可能的情况
即:for(i=1;i<n;i++){
for(j=i+1;j<=n;j++)
判断
}
但是如果按照这样写的话，会tle。我们先分析一下这道题的复杂度，最外层循环是（n-1）内层循环是（n-1+n-2+…+1）=(n-1)*n/2。所以复杂度接近O(n^3)，而且数据n最大为3e5，明显会tle。这时我们就得减少循环个数，接下来就要用数学方法优化算法。
思想
我们先不看这道题，想一组数据，这组数据特征是第一列是递增顺序，第二列无所谓。这一组数据分为2类，第一类是第一列有重复数字 1 2/1 3 第二类是第一列无重复数字 1 2/2 3
注意：分类的时候不需要考虑第二列是否有重复。
实际上这道题目评测的时候所有的数据只可能是两类中的一个，那我们先考虑第二类的情况。
a b 这一组数据是第二类（a<c<e），实际上是否可能存在区间包含只需要检查相邻两个区间是否存在包含关系
c d
e f
证明：如果b>=d 就有包含关系。
如果b<d的时候就无需检查b与f…的大小关系，这时因为
如果[a,b]与 [e,f]存在包含关系即（b>=f）
即d>f，这个就说明[c,d]与 [e,f]存在包含关系。（可以直接检查相邻区间就是上面的黑体字）
如果[a,b]与 [e,f]不存在包含关系即（b<f）
这时就更需要看[c,d]与[e,f]是否存在包含关系
即证
a b 这一组数据是第一类 很明显[a,b]与[a,d]存在包含关系
a d
c e
综上所述：只需要检查相邻两个区间是否存在包含关系
AC代码（我的代码没有加工，不是最优的。但是根据这个思路可以优化代码）

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef   pair<pair<int,int>,int> P;
P p[300002];
bool cmp(P t,P q){
if(t.first.first<q.first.first) return true;
if(t.first.first==q.first.first)  return t.first.second<q.first.second;
if(t.first.first>q.first.first)  return false;
}
int main(){
int n,i;
cin>>n;
for(i=1;i<=n;i++)
{
     cin>>p[i].first.first>>p[i].first.second;
     p[i].second=i;
}
sort(p+1,p+n+1,cmp);
for(i=1;i<n;i++){
      if(p[i].first.first!=p[i+1].first.first&&p[i].first.second<p[i+1].first.second)
            continue;
      else if(p[i].first.first==p[i+1].first.first&&p[i].first.second<p[i+1].first.second)
	  {printf("%d %d\n",p[i].second,p[i+1].second);break;}
     else
	{printf("%d %d\n",p[i+1].second,p[i].second);break;}
}
if(i==n) printf("-1 -1\n");
return 0;
}