题目描述

难度分:$1400$

输入$T(\leq 2 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 10^5$。

每组数据输入$n(2 \leq n \leq 10^5)$，$m(0 \leq m \leq 10^5)$和$m$对数字$(x_i,y_i)$，范围 $[1,n]$且$x_i \neq y_i$。

有$n$个人，编号从$1$到$n$：

• 输入的$m$对数字表示$x_i$和$y_i$互相不认识。
• 不在这$m$对数字中的任何数对，都互相是朋友关系。

注：从图论角度来说，就是一个$m$条边的无向图的补图上的边，都表示朋友关系。

问：序列$[1,2,…,n]$有多少个非空连续子数组$b$，满足$b$中的人两两都是朋友？

注意长度为$1$的$b$一定符合要求。

输入样例

2
3 2
1 3
2 3
4 2
1 2
2 3

输出样例

4
5

算法

动态规划

先将所有的$(x_i,y_i)$放入到一个数组$tup$中（为了方便，读入数据的时候保证$x_i \lt y_i$成立，不成立就交换$x_i$和$y_i$），然后双关键字排序。接下来遍历$tup$构建一个映射$most\_right$“$i \rightarrow$ $i$的右边最远的朋友$j$（满足区间$(i,j]$内的所有人都是$i$的朋友）”，这个很好处理，倒序遍历$tup$时，维护$most\_right[tup[i][0]]=tup[i][1]-1$的最小值即可，这本质是一个递推的DP。不在映射$most\_right$内的$i$，就满足$most\_right[i]=i$。

状态定义

$dp[i]$表示以$i$开头的，满足内部所有人都互相为好友的子数组有多少个。其实我们只要找到$i$的$j=most\_right[i]$即可，因为子数组$[i,k]$，$k \in [i,j]$一定都满足条件，所以一共有$j-i+1$个以$i$开头的子数组满足条件。

状态转移

根据状态定义，状态转移方程为$dp[i]=most\_right[i]-i+1$，最终答案就应该是$\Sigma_{i=1}^{n}dp[i]$。

复杂度分析

时间复杂度

排序的时间复杂度为$O(nlog_2n)$，之后倒序遍历$n$到$1$计算答案时间复杂度为$O(n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

哈希表$most\_right$的空间复杂度为$O(n)$，有$O(n)$个键值对。$(x_i,y_i)$点对有$O(n)$个，即$tup$数组也是$O(n)$规模的。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;
typedef pair<int, int> PII;

int T, n, m, x, y;

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        vector<PII> tup;
        for(int i = 1; i <= m; i++) {
            scanf("%d%d", &x, &y);
            if(x > y) swap(x, y);
            tup.push_back({x, y});
        }
        sort(tup.begin(), tup.end());
        unordered_map<int, int> most_right;
        for(int i = tup.size() - 1; i >= 0; i--) {
            auto& pir = tup[i];
            most_right[pir.first] = pir.second - 1;
        }
        for(int i = 1; i <= n; i++) {
            if(most_right.find(i) == most_right.end()) {
                most_right[i] = n;
            }
        }
        long long ans = 1;
        int mn = most_right[n];
        for(int i = n - 1; i >= 1; i--) {
            mn = min(mn, most_right[i]);
            ans += mn - i + 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}