Solution

首先容易分析有两种走法：

  1. 先右再下(包含只右不下)
  2. 先下再右

对于第1种走法，我们只需要遍历第一行第一个障碍物之前的列，计算每一列遇到第一个格子之前的长度即为贡献。
问题在于如何计算第2种走法的同时不重复计算第1种走法。
下面为了方便我用表示每一行的限制，表示每一列的限制，及第一个遇到的障碍物。

我们此时只需要计算第1种走法无法走到而第2种方法可以走到的格子即可。
有2种格子：

  1. 显然的格子的贡献我们都没有计算，但是在第2种走法的情况下，我们可以走到这些格子，我们将其放入数组中。
  2. 从开始第列被的石子挡住了，因此无法通过第1种走法走到，而可能可以通过第2种走法走到，我们将放入。

逐行扫描从，并将对应的中的列加入到树状数组中，对应的每一行的贡献是。
时间复杂度：

Code

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define lowbit(x) ((x) & -(x))

using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;

constexpr double eps = 1e-8;
constexpr int NINF = 0xc0c0c0c0;
constexpr int INF = 0x3f3f3f3f;
constexpr ll LNINF = 0xc0c0c0c0c0c0c0c0;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr ll mod = 1e9 + 7;
constexpr ll N = 2e5 + 5;

vector<int> sz[N];

template <typename T> struct fenwick_tree {
    int n;
    vector<T> t;
    fenwick_tree() : n(0) {}
    fenwick_tree(int n) : n(n), t(n + 1) {}

    void add(int p, T x) {
        while (p <= n) {
            t[p] += x;
            p += lowbit(p);
        }
    }

    T sum(int x) {
        T s = 0;
        while (x > 0) {
            s += t[x];
            x -= lowbit(x);
        }
        return s;
    }

    T sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int h, w, m;
    cin >> h >> w >> m;
    vector<int> climit(h + 1, w + 1), rlimit(w + 1, h + 1);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        climit[x] = min(climit[x], y);
        rlimit[y] = min(rlimit[y], x);
    }
    ll ans = 0;
    for (int i = 1; i < climit[1]; i++) {
        ans += rlimit[i] - 1;
        sz[rlimit[i]].push_back(i);
    }
    for (int i = climit[1]; i <= w; i++) {
        sz[1].push_back(i);
    }
    fenwick_tree<int> T(w);
    for (int i = 1; i < rlimit[1]; i++) {
        for (int j : sz[i]) T.add(j, 1);
        ans += T.sum(climit[i] - 1);
    }
    cout << ans << '\n';

    return 0;
}