蓝桥备战-区间嵌套--前缀和做法

题目：

思路：

区间按照左端点排序，如果左端点相等，则按照右端点逆序排序(右端点越大越好)，从前往后一次枚举每个区间，如果一个区间后面存在一个区间的右端点小于等于我这个区间的右端点那么即存在。所以我们只需要看后面是否存在一个最小的右端点是否小于等于该区间的右端点即可。

创建一个后缀和维护区间右端点最小值。

代码：

#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> PII;
const int N = 3e5 +10;

int n;

struct Range
{
    int x, y, id;
    bool operator < (const Range &r)
    {
        if (x != r.x)   return x < r.x;
        else return r.y < y;
    }
}range[N];

Range b[N];

int main()
{
    cin >> n;
    for (int i = 0; i < N; i++)
        b[i].y = 0x3f3f3f3f;
    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b, i};
    }

    sort (range, range + n);

    for (int i = n - 1; i >= 0; i--)
    {
        b[i] = b[i + 1];
        if (b[i].y >= range[i].y)
            b[i] = range[i];
    }

    for (int i = 0; i < n; i++)
    {
        if (range[i].y >= b[i + 1].y)
        {
            cout << b[i + 1].id + 1 << " ";
            cout << range[i].id + 1;
            return 0;
        }
    }

    cout << "-1 -1";
    return 0;
}

另一种比较巧妙的思路：

我们只需要枚举相邻区间即可，因为如果枚举相邻区间的时候没有出现右端点逆序的(可等于)，便代表所有区间的右端点是升序的(不包含等于)。那么及不存在嵌套区间。所以想要出现嵌套区间相邻区间必然存在右端点逆序。

代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 3e5 +10;

int n;

struct Range
{
    int x, y, id;
    bool operator < (const Range &r)
    {
        if (x != r.x)   return x < r.x;
        else return r.y < y;
    }
}range[N];


int main()
{
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b, i};
    }

    sort (range, range + n);

    for (int i = 0; i < n - 1; i++)
    {
        if (range[i].y >= range[i + 1].y)
        {
            cout << range[i + 1].id + 1 << " ";
            cout << range[i].id + 1;
            return 0;
        }
    }
    cout << "-1 -1";
    return 0;
}