I题

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
vector<int> h[1000005];//邻接表

bool check(int l,int r)//检查r是否可以加入[l,r-1]的友好区间区间组成新的友好区间
{
    auto ptr1=lower_bound(h[r].begin(),h[r].end(),l);
    auto ptr2=lower_bound(h[r].begin(),h[r].end(),r-1);
    if(ptr1==h[r].end() || ptr2==h[r].end())return false;//没找到
    
    if(ptr2-ptr1+1==r-l && *ptr1==l && *ptr2==r-1)return true;//说明r点与[l,r-1]上的点都有边
    else return false;
}

void solved()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)//建有向边(大-->小)
    {
        int u,v;
        cin>>u>>v;
        if(u<v)swap(u,v);
        h[u].push_back(v);
    }
    
    for(int i=1;i<=n;i++)//邻接表排序(用于后面二分查找)
        sort(h[i].begin(),h[i].end());
    
    int ans=0;
    for(int i=1,j=1;j<=n;)//快慢双指针枚举区间左右端点
    {
        while(j+1<=n && check(i,j+1))j++;
        ans+=j-i+1;//以i为左端点的友好区间的贡献
        
        if(i==j)i++,j++;
        else i++;
    }
    
    cout<<ans<<endl;
}

signed main()
{
    solved();
    return 0;
}