###### tags: `CP`
# Codeforces Round #837 (Div. 2)解題心得
這次參加Codeforces Round #837 (Div. 2)，希望能夠將打Codeforces競賽成為習慣，以訓練DEBUG的能力和加快思考速度。

*A. Hossam and Combinatorics*
若a_i,a_j滿足|a_i−a_j|=max_1≤p,q≤n|a_p−a_q|，則可以發現a_i,a_j是此數列的最大值和最小值，所以便利整個陣列，便可以得知此數列中與最大值和最小值相同的數共有幾個，因為算法設計，令r為最大值在數列中出現的次數，l為最小值在數列中出現的次數，若ma == mi時，其組合方式共有(l - 1) * r種；否則有l * r * 2種。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using ll = long long;

int main()
{
    int t, n; cin >> t;
    while(t--) {
        ll l = 0, r = 0;
        cin >> n;
        int mi = 1e6, ma = 0;
        vector <int> v(n);
        for(auto &i : v) {
            cin >> i;
            mi = min(mi, i);
            ma = max(ma, i);
        }

        for(auto i : v) {
            if(i == mi) l++;
            if(i == ma) r++;
        }
        if(ma == mi) cout << (l - 1) * r << "\n";
        else cout << l * r * 2 << "\n";
    }
}

*B. Hossam and Friends*
這題是在競賽結束之後才解出來，給定n個人，m組(x, y)，表示x, y之間相互不認識，問有多少組subsegment(a, b)(表示(a, b)間的人都相互認識)。解題思路意外簡單，若是未出現相互不認識的人則將值累加，否則將值更新為(x, y)之間的距離。

Example:
8
1 3
2 6

1 2 3 4 5 6 7 8
1 2 2 3 4 4 5 6

Ans = 1 + 2 + 2 + 3 + 4 + 4 + 5 + 6 = 27

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main()
{
    int t, n, m; cin >> t;
    while(t--) {
        cin >> n >> m;
        vector <int> v(n + 1, 0);
        while(m--) {
            int x, y; cin >> x >> y;
            if(x > y) swap(x, y);
            v[y] = max(v[y], x);
        }
        ll ans = 0;
        for(int i = 1; i <= n; ++i) {
            if(i != 1) v[i] = max(v[i - 1], v[i]);
            ans += i - v[i];
        }
        cout << ans << "\n";
    }
}