Codeforces Round 837题解（A、B）

A. Hossam and Combinatorics

\(|a_i - a_j|\)最大的就是最大值和最小值，注意要开long long。

int n;
int a[N];
 
void solve() {
    cin >> n;
    int min_v = INF, max_v = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        min_v = min(min_v, a[i]);
        max_v = max(max_v, a[i]);
    }
    int cnt_min = 0, cnt_max = 0;
    if (min_v == max_v) {
        cout << n * (n - 1) << '\n';
        return;
    }
    for (int i = 1; i <= n; i ++) {
        if (a[i] == min_v) cnt_min ++;
        if (a[i] == max_v) cnt_max ++;
    }
    cout << cnt_min * cnt_max * 2 << '\n';
}

B. Hossam and Friends

考虑对每一个\(l\)，有那些\(r\)满足\([l, r]\)中的朋友都互相认识。

设共有\(m\)各互相不认识的对\((l, r)\)，则所有小于\(l\ge\)当前枚举到的\(i\)的\((l, r)\)对中最小的\(r\)的下标都可以作为当前\(i\)的\(r\)。

那么我们开个优先队列维护即可。

 
int n, m;
vector<int> bag[N];
priority_queue<PII, vector<PII>, greater<>> pq;
 
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) bag[i].clear();
    while (!pq.empty()) pq.pop();
    for (int i = 1; i <= m; i ++) {
        int l, r;
        cin >> l >> r;
        if (l > r) swap(l, r);
        bag[l].push_back(r);
    }
    int ans = 0;
    for (int i = n; i >= 1; i --) {
        for (auto j : bag[i]) pq.push({j, i});
        if (pq.empty()) {
            ans += n - i + 1;
            continue;
        }
        ans += pq.top().first - i;
    }
    cout << ans << '\n';
}