ABC186F

Lyccrius · 2023-05-09 11:59:39 · 题解

行和列分开处理。

考虑先往下走再往右走，走到 (i, 1) 时，贡献为 r[i] - 1，当 r[i] = 1 时无法继续往下走。

找到第一个 r[i] = 1 的 i，(i, h] 行换一种方式处理：将 i 加入第 r[i] + 1 列的标记区。

一个行标记 x 出现在第 y 列的标记区，表示第 x 行被障碍物阻挡，且第 x 行的 [y, w] 部分需要通过先往右走再往下走计算贡献。

考虑先往右走再往下走，走到 (1, i) 时，贡献为标记区前缀并集内小于 c[i] 的元素个数，当 c[i] = 1 时无法继续往右走。

可能文字无法很好的表述，可以画图模拟尝试理解。

计算标记前缀并集元素个数可以使用权值线段树维护。

int main() {
    std::cin >> h >> w >> m;
    for (int i = 1; i <= h; i++) r[i] = w + 1;
    for (int i = 1; i <= w; i++) c[i] = h + 1;
    for (int i = 1; i <= m; i++) {
        std::cin >> x >> y;
        r[x] = std::min(r[x], y);
        c[y] = std::min(c[y], x);
    }
    bool flag = true;
    for (int i = 1; i <= h; i++) {
        if (flag) {
            ans += r[i] - 1;
            if (r[i] <= w) t[r[i] + 1].push_back(i);
            if (r[i] == 1) flag = false;
        } else {
            t[2].push_back(i);
        }
    }
    for (int i = 1; i <= w; i++) {
        if (c[i] == 1) break;
        for (auto j : t[i]) SGT.Add(1, 1, h, j, 1);
        ans += SGT.Ask(1, 1, h, 1, c[i] - 1);
    }
    std::cout << ans << '\n';
    return 0;
}