[Q] https://atcoder.jp/contests/abc186/tasks/abc186_f

考察
1. 右下に移動した場合に、各列で何マスとるかを数列Dにすることはできる。
2. 下右に移動した場合に、各行で何マスとるかを数列Rにすることはできる。
3. 総和をとると、重複してカウントしてしまう。
4. 右下は全部加算するとして、下右のパターンで、増加分だけ加算したい。
5. 各行で0~rマスまで取るわけだけど、その中に自分のindexよりも小さいD[0] ~ D[r]の値の数が、増加分になる。
6. D[0] ~ D[r]の累積和はBITで管理すればいい。rは小さい値から挿入したい。
7. クエリ先読みをする

5 4 1
1 2
のとき注意。

  5 0 0 0 // 5 0 5 5ではなく、5 0 0 0にする
1 x o x x
4 x x x x
4 x x x x
4 x x x x
4 x x x x

D[] = 5 0 0 0
R[] = 1 4 4 4 4

まずDを足す。
ans = 5 + 0 + 0 + 0

次にクエリ逆読み。Rについて、R[i]の小さい順に探索。{r, id}でsort。
0~rまで、BITにD[r]を加算していく。
そうすれば、ans += BIT.sum(id)が、Rの増加分となる。

ans = 17マス

実装

// BIT
// 内部的にindexを+1して格納しているので注意
// https://atcoder.jp/contests/abc174/submissions/21572028
template<ll BT>
struct Bit
{
  ll dat[BT+10]{};
  void add(ll i, ll x){
    ++i;
    for(; i<BT; i += i&-i) dat[i] += x;
  }
  ll sum(ll i){ // [0, i]
    if (i<0) return 0;
    if (i>=BT-1) i = BT-2;
    ++i;
    ll res = 0;
    for(; i>0; i -= i&-i) res += dat[i];
    return res;
  }
  ll rangesum(ll L, ll R){ // [L, R]
    return sum(R) - sum(L-1);
  }
};

int main() {
  cincout();

  ll H, W, M;
  cin >> H >> W >> M;
  Bit<200020> bt;
  vector<ll> D(W, H);
  vector<ll> R(H, W);
  rep(i, M){
    ll y, x;
    cin >> y >> x;
    --y, --x;
    chmin(R[y], x);
    chmin(D[x], y);
  }
  vector<pll> Q; // rx, i
  for(ll i = R[0] + 1; i < W; ++i){ // R[0]より先はとらない
    D[i] = 0;
  }

  // クエリ先読み
  rep(i, D[0]){ // D[0]までしか見ない。Hまで見ない。
    Q.emplace_back(R[i], i);
  }
  sort(all(Q));
  ll ans = 0;
  rep(i, R[0]){ // R[0]までしか見ない。Wまで見ない。
    ans += D[i];
  }
  ll st = 0;
  rep(i, D[0]){ // D[0]までしか見ない。Hまで見ない
    auto[r, id] = Q[i];
    while(st < r){
      bt.add(D[st], 1);
      ++st;
    }
    ans += bt.sum(id);
  };
  cout << ans << endl;
}

Q. 方針見えたのに永遠にWA？
A. D[0]から先を見ないとか、R[0]以降の値を0にするとかを忘れた。

https://atcoder.jp/contests/abc186/submissions/45068846