英文题干

There are n people standing in a line, numbered from 1 to n from left to right. Among these people, there are m pairs of friends. Define an interval as friendly if and only if every pair of people within the interval are friends. How many friendly intervals are there?

Input:

The first line contains two integers and (), representing the number of people and the number of pairs of friends, respectively.

The next lines each contain two integers and (), representing a pair of friends.

It is guaranteed that there are no duplicate friend pairs in the input.

Output:

Output a single integer representing the number of friendly intervals.

中文题干

有n个人站在一条线上，从左到右编号为1到n。在这些人中，有m对朋友。

定义一个区间为友好区间，当且仅当该区间内的每对人都是朋友时。

有多少个友好区间？（注：此处朋友不具有传递性，且长度为1的区间也是友好区间）

思路

  1. 我们考虑按照类似求前缀和的方式求区间总数，首先记录2到n每个序号的人能向前扩展到的最小序号的人（如果中间断了就说明不能继续扩展了，因为不具有传递性）

  2. 然后按从小到大的顺序依次合并，计算区间个数。i 能贡献的区间数就是 , 并且更新 i 能向前扩展到的最小序号为 （走不了回头路，前面断了的后面不可能再成为友好区间）。最后加上长度1的区间即可。

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1e6 + 10;

int n, m;
ll ans = 0;
vector<int> mp[maxn];
int expand[maxn];  // 以 i 结尾的最长友好区间的左端点

inline bool cmp(int x, int y) {
    return x > y;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    int fr1, fr2;
    for (int i = 1; i <= m; i++) {
        cin >> fr1 >> fr2;
        if (fr1 < fr2)
            swap(fr1, fr2);
        mp[fr1].push_back(fr2);  // 把较小的那个编号存入较大的编号对应的朋友列表中
    }

    for (int i = 2; i <= n; i++) {
        sort(mp[i].begin(), mp[i].end(), cmp);
        int faridx = i;  // 记录区间能扩展到的最远位置（序号最小的人）
        for (int j = 0; j < mp[i].size(); j++) {
            if (mp[i][j] == faridx - 1) {
                faridx--;
                expand[i] = faridx;
            }
            else {
                break;
            }
        }
    }

    // 处理长度为1的区间
    for (int i = 1; i <= n; i++) {
        if (expand[i] == 0) {
            expand[i] = i;
        }
    }

    // 计算友好区间数量
    for (int i = 2; i <= n; i++) {
        ans += min(i - expand[i], i - expand[i - 1]);
        expand[i] = max(expand[i], expand[i - 1]);
    }

    cout << ans + n << endl; // 加上长度为1的区间

    return 0;
}
// Inspired by LJY