B. Hossam and Friends

B. Hossam and Friends

题目大意：

有\(n\)对朋友，其中\(m\)对朋友互相不认识，让你选区间，最多可以选多少区间，区间中没有互相不认识的朋友

思路：

遍历每个点作为区间的左端点，必须满足\(a[i]\le a[i+1]\)(\(a[i]\)存储以\(i\)做左端点，右端点的最大值)，

证明：即前一项的右端点不可能比这一项的右端点大，如果大的话，说明\([i,a[i]]\)区间没有一对互相不认识的朋友，\([i+1,a[i]]\)是他的子区间，此时\(a[i]\)可以是\(i+1\)的右端点，与假设不符

所以可以从后向前递推\(a[i]\)的值，\(ans+=a[i]-i+1\)

code:

int n, m;
int a[N];
void solved()
{
    cin >> n >> m;
    for (int i = 1; i <= n + 1; ++i)
    {
        a[i] = n;
    }
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        cin >> x >> y;
        if (a[min(x, y)] > max(x - 1, y - 1))
            a[min(x, y)] = max(x - 1, y - 1);
    }
    ll ans = 0;
    for (int i = n; i > 0; --i)
    {
        if (a[i] > a[i + 1])
            a[i] = a[i + 1];
        ans += a[i] - i + 1;
    }
    cout << ans << endl;
}