明明看着不难的题目，却意外的卡人。
思路
考虑两头奶牛可以成为朋友条件是什么。
存在一条路径连接这两头奶牛。
且除去端点外的路径上的所有点的编号小于两端点的较小值。
充分必要性都比较显然。
如何维护。
我们可以从小到大加入点，维护这些路径。
对于每个点维护一个 \(\text{set}\)。
表示这个点所在的联通块可以去到的还没有加进来的点有多少个。
因为没有加进来的点都比已经加进来的点要大。
那么可以启发式合并维护一下就可以了。
Code
/**
* @file P8907.cpp
* @author mfeitveer
* @date 2023-11-22
*
* @copyright Copyright (c) 2023
*
*/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 1000010;
const int mod = 998244353;
int n, m, fa[N]; i64 ans = 0;
vector<int> to[N];
set<int> q[N];
inline void merge(int x, int y)
{
if(q[x].size() < q[y].size())
swap(q[x], q[y]);
for(auto i : q[y]) q[x].insert(i);
q[y].clear();
}
inline void calc(int x, int y)
{
while(q[x].empty() == 0 && *q[x].begin() <= y)
q[x].erase(q[x].begin());
}
inline int gf(int x)
{ return fa[x] == x ? x : fa[x] = gf(fa[x]); }
inline void solve()
{
cin >> n >> m;
fro(i, 1, m)
{
int x, y;
cin >> x >> y;
to[x].push_back(y);
to[y].push_back(x);
}
iota(fa + 1, fa + n + 1, 1);
fro(i, 1, n)
{
sort(to[i].begin(), to[i].end());
for(auto j : to[i]) if(j > i)
q[i].insert(j);
int num = q[i].size();
for(auto j : to[i]) if(j < i && i != gf(j))
merge(i, gf(j)), fa[gf(j)] = i;
calc(i, i), ans += q[i].size() - num;
}
cout << ans << "\n";
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 256;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
solve();
return 0;
}