CCF-CSP认证考试 202303-5 施肥 35/60/75/100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202303-5 施肥

时间限制： 2.0s
内存限制： 1.0GB

问题描述

春天到了，西西艾弗岛上的 $n$ 块田地需要施肥了。 $n$ 块田地编号为 $\cdots, n$ ，按照编号从小到大的顺序排成一列。

为了给田地施肥，顿顿准备了 $m$ 辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第 $i$ 辆施肥车只能恰好从第 $l_i$ 块田地开到第 $r_i$ 块田地，并给编号在 $l_i$ 与 $r_i$ 之间的田地（包含 $l_i$ 和 $r_i$ ）都施一遍肥。其中 $\leq l_i < r_i \leq n$ 。

顿顿希望制定一个施肥的计划。首先，他将选定二元组 $\leq L < R \leq n)$ ，并选择只给编号在 $L, R$ 之间（包含 $L, R$ ）的田地施肥。接着，他会从使用这 $m$ 辆施肥车中的一部分（或全部）对田地施肥。他想要保证：编号在 $L$ 和 $R$ 之内的田地至少被某一辆施肥车施了一次肥，且编号范围外的田地都没有被施过肥。

现在，他想知道，他能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。

输入格式

从标准输入读入数据。

第一行输入两个正整数 $n, m$ ，表示田地的块数和施肥车的辆数。数据保证 $\leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5$ 。

接下来 $m$ 行，第 $i$ 行输入两个正整数 $l_i, r_i$ ，表示第 $i$ 辆施肥车的施肥范围从第 $l_i$ 块田地到第 $r_i$ 块田地。数据保证 $\leq l_i < r_i \leq n$ 。

输出格式

输出到标准输出。

输出一个正整数，表示顿顿能够选择多少种不同的二元组 $(L, R)$ 作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。

样例输入1

样例输出1

样例解释

在这组样例中，顿顿可以选择 $6$ 种不同的二元组 $(L, R)$ 。

第一种：选择 $(L, R) = (1, 2)$ ，并只选取第 $1$ 个施肥车施肥。

第二种：选择 $(L, R) = (3, 4)$ ，并只选取第 $2$ 个施肥车施肥。

第三种：选择 $(L, R) = (2, 3)$ ，并只选取第 $3$ 个施肥车施肥。

第四种：选择 $(L, R) = (1, 4)$ ，并选取第 $1$ 个和第 $2$ 个施肥车施肥。

第五种：选择 $(L, R) = (1, 3)$ ，并选取第 $1$ 个和第 $3$ 个施肥车施肥。

第六种：选择 $(L, R) = (2, 4)$ ，并选取第 $2$ 个和第 $3$ 个施肥车施肥。

子任务

测试点编号	$n\le$	$m\le$	特殊性质
1	18	18
2	18	18
3	18	18
4	50	50
5	50	50
6	400	400
7	400	400
8	3000	3000
9	3000	3000
10	3000	3000
11	3000	3000
12	3000	3000
13	200000	200000	A
14	200000	200000	A
15	200000	200000	A
16	200000	200000
17	200000	200000
18	200000	200000
19	200000	200000
20	200000	200000

特殊性质 A：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意 $\leq i < j \leq m$ ， $l_i < l_j, r_i < r_j$ 或 $l_i > l_j, r_i > r_j$ 。

35 分题解（测试点 1~7）

对于每组 $(L, R)$ ，去判断是否能选出若干辆施肥车，使他们的区间并为 $[L, R]$ 。

选择施肥车的策略是只要满足 $L\leq l_i<r_i\leq R$ 的施肥车就选，选完一辆车就把这辆车能覆盖坐标的 vis $+ 1$ ，最后判断从 $L$ 到 $R$ 中的所有坐标是否都是非零。

但是对每一辆车一个个更新速度过慢，考虑差分的算法，如果选 $l_i,r_i]$ 的这辆车，就将 $vis[l_i]+1,vis[r_i+1]-1$ ，判断完所有车后，直接对 vis 数组求个前缀和即可恢复。

时间复杂度： $\mathcal{O}(n^3+n^2m)$ 。

35 分参考代码（运行超时，5.050MB）

/*
    Created by Pujx on 2024/3/23.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

pii a[N];
int n, m, t, k, q;

void work() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].ft >> a[i].se;
    int ans = 0;
    for (int l = 1; l <= n; l++)
        for (int r = l + 1; r <= n; r++) {
            vector<int> vis(n + 2);
            for (int i = 1; i <= m; i++)
                if (l <= a[i].ft && a[i].se <= r)
                    vis[a[i].ft]++, vis[a[i].se + 1]--;
            bool flag = true;
            for (int i = l; i <= r; i++)
                flag &= (vis[i] += vis[i - 1]) > 0;
            ans += flag;
        }
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

60 分题解（测试点 1~12）

枚举右端点 $R$ ，计算有多少个 $L$ 满足条件。

从 $1$ 到 $m$ 遍历 $R$ 。

设 $a_i$ 表示对于每个 $i\leq R$ ，右端点不大于 $R$ 的所有覆盖 $i$ 的区间中，左端点的最大值为多少。对每一条右端点为 $R$ 的区间 $l_i,R]$ ，用 $l_i$ 更新（取最大值） $l_i,R]$ 中的所有 $a_i$ 即可维护 $a_i$ 。

如果 $(L, R)$ 满足条件，当且仅当 $\forall i\in [L,R]$ ， $a_i\leq L$ ，即为了覆盖 $i$ 这个点，选取的线段的左端点不能比 $L$ 小。但要想覆盖到 $i$ 这个点，要保证 $i+1,i+2,\cdots,R$ 均能被覆盖到，取后缀最小值即可。记 $suf_i$ 为后缀最小值，即 $suf_i=\min\limits_{j=i}^Ra_i$ 。

最后，该 $R$ 值对答案的贡献为 $\sum\limits_{i=1}^R[suf_i==i]$ ，即 $suf_i$ 与 $i$ 相等的数量。

时间复杂度： $\mathcal{O}(nm+n^2)$ 。

60 分参考代码（运行超时，10.55MB）

/*
    Created by Pujx on 2024/3/23.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N], suf[N];
int n, m, t, k, q;
vector<int> R[N];

void work() {
    cin >> n >> m;
    for (int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        R[r].emplace_back(l);
    }
    int ans = 0;
    for (int r = 1; r <= n; r++) {
        for (auto l : R[r])
            for (int i = l; i <= r; i++)
                a[i] = max(a[i], l);
        suf[r] = a[r];
        for (int l = r - 1; l; l--)
            ans += (suf[l] = min(suf[l + 1], a[l])) == l;
    }
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

75 分题解（测试点 1~15）

根据题目中给定性质 A 的特殊限制，即给定的区间满足偏序关系，可以将其划分成若干组连续的集合。

在这里插入图片描述

特殊地，如图中的第 $5, 6$ 两条线段，由于田地编号为整数，只要考虑整数是否连续，并不一定要有交集，才可以分在同一组中。

对于每一组来说，只要选择连续（按 $l_i$ 排好序后的序号）的一定数量的线段，即可构成一个不同 $(L, R)$ 组。因此，如果该组有 $c n t$ 个线段，对答案的贡献为 $\dfrac{cnt(cnt+1)}{2}$ 。

时间复杂度：测试点 $1\sim 12$ ： $\mathcal{O}(nm+n^2)$ ；测试点 $13\sim 15$ ： $\mathcal{O}(m)$ 。

75 分参考代码（78ms，9.031MB）

/*
    Created by Pujx on 2024/3/23.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N], suf[N];
pii v[N];
int n, m, t, k, q;
vector<int> R[N];

void work() {
    cin >> n >> m;
    if (n <= 3000 && m <= 3000) {
        // 测试点 1 ~ 12
        for (int i = 1, l, r; i <= m; i++) {
            cin >> l >> r;
            R[r].emplace_back(l);
        }
        int ans = 0;
        for (int r = 1; r <= n; r++) {
            for (auto l : R[r])
                for (int i = l; i <= r; i++)
                    a[i] = max(a[i], l);
            suf[r] = a[r];
            for (int l = r - 1; l; l--)
                ans += (suf[l] = min(suf[l + 1], a[l])) == l;
        }
        cout << ans << endl;
    }
    else {
        // 测试点 13 ~ 15
        for (int i = 1; i <= m; i++) cin >> v[i].ft >> v[i].se;
        sort(v + 1, v + m + 1);
        i64 ans = 0;
        for (int l = 1, r = 1; l <= m; r = l = r + 1) {
            int rmax = v[l].se;
            while (r + 1 <= m && v[r + 1].ft <= rmax + 1) rmax = max(rmax, v[++r].se);
            int cnt = r - l + 1;
            ans += 1ll * cnt * (cnt + 1) / 2;
        }
        cout << ans << endl;
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

100 分题解

使用分治算法。通过分治，我们可以得知 $[l, mi d], [mi d + 1, r]$ 区间内对 $(L, R)$ 总数的贡献，那么仅需要考虑与这两个区间均相交的 $(L, R)$ 的个数。

对于每个 $L\in[l,mid]$ ，计算出 $a_L$ 的最大值，满足 $L,a_L]$ 可以由包含于 $[L, mi d]$ 的区间取并集得到。

对于每个 $R\in[mid+1,r]$ ，计算出 $b_R$ 的最小值，满足 $b_R,R]$ 可以由包含于 $[mi d + 1, R]$ 的区间取并集得到。

通过两棵线段树维护（ $A$ 维护数组 $a$ ， $B$ 维护数组 $b$ ），需要单间修改和区间查询最值。实际上 $A$ 只用维护最大值， $B$ 只用维护最小值，为了写法方便均将最大值和最小值一起维护。

$(L, R)$ 如果是一个满足条件的二元组，则横跨两块的区间可以覆盖到 $a_L+1,mid]$ 和 $mid+1,b_R-1]$ 。

对于每个 $L\in[l,mid]$ ，计算出 $x_L$ 的最小值，满足 $x_L\geq mid + 1$ ，且 $L,x_L]$ 可以由包含于 $[L, R]$ 的区间取并集得到（不存在的可以赋为 $+\infty$ ）。

对于每个 $R\in[mid+1,r]$ ，计算出 $y_R$ 的最大值，满足 $y_R\leq mid$ ，且 $y_R,R]$ 可以由包含于 $[L, R]$ 的区间取并集得到（不存在的可以赋为 $-\infty$ ）。

通过两棵线段树维护（ $X$ 维护数组 $x$ ， $Y$ 维护数组 $y$ ），需要单间修改和区间查询最值。实际上 $X$ 只用维护最小值， $Y$ 只用维护最大值，为了写法方便均将最大值和最小值一起维护。
由于题目考虑的是整数的区间并而非实数的区间并，在维护线段树 $X, Y$ 时（调用 modify 函数）要注意 $mi d$ 附近的情况，如果写到上一个 if 的 else 分支中，会导致后续进行的是实数的区间并（认为整数 $mi d$ 和 $mi d + 1$ 无法进行区间并）而造成错误，具体示例可以参考下面这个样例。
4 2
1 2
3 4
此外还需要特殊考虑横跨两块的区间对 $x, y$ 的影响（该影响可能不在线段树中体现出来）。

$(L, R)$ 所满足的条件可以进一步化为 $x_L\leq R,y_R\geq L$ ，如此变成了一个典型的静态二维数点的问题。

将 $L,x_L),(y_R,R)$ 的满足上述条件的二维点按照左端点值、右端点值、 $L, R$ 的关系进行排序。
采用树状数组（当然也可以使用线段树，只不过不想再写一棵了）维护支持单点修改的区间前缀和。
对于 $L,x_L)$ ，将 $x_L$ 的值 $+ 1$ ；
对于 $y_R,R)$ ，将答案加上 $R$ 的前缀和。

注意在线段树/树状数组维护的过程中，要根据区间大小来建立对应大小的线段树/树状数组，或者可以通过清空原有线段树/树状数组，否则可能超时。

时间复杂度： $\mathcal{O}((n+m)\log^2n)$ 。

100 分参考代码（734ms，38.00MB）

/*
    Created by Pujx on 2024/3/23.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include "debug.h"
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N], b[N], x[N], y[N];
int n, m, t, k, q;
i64 ans;
vector<int> L[N], R[N];

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r; T mx, mn; } tr[N << 2];
    void pushup(int s) {
        tr[s].mx = max(tr[ls].mx, tr[rs].mx);
        tr[s].mn = min(tr[ls].mn, tr[rs].mn);
    }
    void build(int l, int r, int s = 1) {
        tr[s].l = l, tr[s].r = r;
        tr[s].mx = -inf, tr[s].mn = inf;
        if (l == r) return;
        int mid = l + r >> 1;
        if (l <= mid) build(l, mid, ls);
        if (mid < r) build(mid + 1, r, rs);
        pushup(s);
    }
    void modify(int p, T val, int s = 1) {
        if (tr[s].l == tr[s].r) {
            tr[s].mx = max(tr[s].mx, val);
            tr[s].mn = min(tr[s].mn, val);
            return;
        }
        int mid = tr[s].l + tr[s].r >> 1;
        if (p <= mid) modify(p, val, ls);
        else modify(p, val, rs);
        pushup(s);
    }
    T queryMax(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].mx;
        int mid = tr[s].l + tr[s].r >> 1;
        T ans = numeric_limits<T>::min();
        if (l <= mid) ans = max(ans, queryMax(l, r, ls));
        if (mid < r) ans = max(ans, queryMax(l, r, rs));
        return ans;
    }
    T queryMin(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].mn;
        int mid = tr[s].l + tr[s].r >> 1;
        T ans = numeric_limits<T>::max();
        if (l <= mid) ans = min(ans, queryMin(l, r, ls));
        if (mid < r) ans = min(ans, queryMin(l, r, rs));
        return ans;
    }
};
SegmentTree<int> A, B, X, Y;

template <typename T> struct Fenwick {
    int n;
    vector<T> a;
    Fenwick(int n = 0) { init(n); }
    void init(int n) { this->n = n; a.assign(n + 1, T()); }
    void add(int x, T v) {
        for (int i = x; i <= n; i += i & -i)
            a[i] += v;
    }
    T sum(int x) {
        auto ans = T();
        for (int i = x; i; i -= i & -i)
            ans += a[i];
        return ans;
    }
    T sum(int l, int r) { return sum(r) - sum(l - 1); }
    void set(int x, T v) { add(x, v - sum(x, x)); }
};
Fenwick<int> fen;

void calc(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    calc(l, mid), calc(mid + 1, r);

    A.build(l, mid), B.build(mid + 1, r), X.build(l, mid + 1), Y.build(mid, r);
    for (int i = l; i <= r; i++) a[i] = y[i] = -inf, b[i] = x[i] = inf;

    for (int i = mid; i >= l; i--)
        for (auto j : L[i]) {
            if (j > r) continue;
            else if (j <= mid) a[i] = max(a[i], j);
            else x[i] = min(x[i], j);
            if (j >= mid) Y.modify(j, i);
        }
    for (int i = mid + 1; i <= r; i++)
        for (auto j : R[i]) {
            if (j < l) continue;
            else if (j >= mid + 1) b[i] = min(b[i], j);
            else y[i] = max(y[i], j);
            if (j <= mid + 1) X.modify(j, i);
        }

    vector<array<int, 3>> v;
    for (int i = mid; i >= l; i--) {
        if (a[i] != -inf) {
            a[i] = max(a[i], A.queryMax(i, min(mid, a[i] + 1)));
            A.modify(i, a[i]);
            x[i] = min(x[i], X.queryMin(i, a[i] + 1));
        }
        if (x[i] != inf) v.push_back({i, x[i], 0});
    }
    for (int i = mid + 1; i <= r; i++) {
        if (b[i] != inf) {
            b[i] = min(b[i], B.queryMin(max(mid + 1, b[i] - 1), i));
            B.modify(i, b[i]);
            y[i] = max(y[i], Y.queryMax(b[i] - 1, i));
        }
        if (y[i] != -inf) v.push_back({y[i], i, 1});
    }

    sort(all(v));
    fen.init(r - l + 1);
    for (auto t : v) {
        if (!t[2]) fen.add(t[1] - l + 1, 1);
        else ans += fen.sum(t[1] - l + 1);
    }
}

void work() {
    cin >> n >> m;
    for (int i = 1, l, r; i <= m; i++) {
        cin >> l >> r;
        L[l].emplace_back(r);
        R[r].emplace_back(l);
    }
    calc(1, n);
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.in", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\data.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
#pragma ... 是用来开启 O2、O3 等优化加快代码速度。
中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
"debug.h" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。