AC 38，WA 2，已经麻木了（）

为方便计算将 $(0, n)$ 视为黑傀儡，具体思路是把黑傀儡分别按照 $x$ 和 $y$ 排序，然后按第一关键字 $x$ 从小到大、第二关键字 $y$ 从小到大枚举黑傀儡，然后倍增得到这个黑傀儡左面一列或右面一列的这个黑傀儡上方的最近的黑傀儡，观察这两个黑傀儡（如果存在的话）能否走到来判断这个黑傀儡是否能走到。

统计答案就是统计每一列最下方黑傀儡是否能走到即可。

s 为输入顺序，sr 为 $x$ 优先，sc 为 $y$ 优先，有时 i、x、r 或 j、y、c 表示一个东西。

# include <ciso646>
# include <cstdio>
# include <algorithm>

namespace Main {
    namespace Source {
        typedef signed int dint;
        typedef short unsigned int hu;
        typedef unsigned int uint;
    }
    using namespace Source;
    enum { M = (const uint)2e5, Log = 17 };
    struct square {
        uint i, j, id;
        bool cv;
        square() : cv(false) {}
        square(const uint i, const uint j, const uint id, const bool cv) : i(i), j(j), id(id), cv(cv)
        {}
        inline const square& read(const uint id)
        { scanf("%u%u", &i, &j), this->id = id; return *this; }
        friend inline const bool cmpi(const square& a, const square& b)
        { return a.i == b.i ? a.j < b.j : a.i < b.i; }
        friend inline const bool cmpj(const square& a, const square& b)
        { return a.j == b.j ? a.i < b.i : a.j < b.j; }
    };
    static uint n, m;
    static square s[M + 1];
    static square sr[M + 1], sc[M + 1];
    static uint ans;
    extern inline const bool cmpi(const square&, const square&);
    extern inline const bool cmpj(const square&, const square&);
    static inline const bool get(const uint r, const uint c) {
        uint t(0), u(0);
        for (hu j(Log); j <= Log; --j)
            if ((t | 1 << j) <= m and sc[t | 1 << j].j < c) t or_eq 1 << j;
        if (++t > m or sc[t].j != c or sc[t].i >= r) return false;
        for (hu j(Log); j <= Log; --j)
            if (t + (u | 1 << j) <= m and sc[t + (u | 1 << j)].j == c and sc[t + (u | 1 << j)].i < r)
                u or_eq 1 << j;
        return s[sc[t += u].id].cv;
    }
    static inline const void main() {
        scanf("%u%u", &n, &m), sc[0] = sr[0] = s[0] = square(0, n, 0, true);
        for (register uint i(1); i <= m; ++i) sc[i] = sr[i] = s[i].read(i);
        std::sort(&sr[0], &sr[m] + 1, cmpi), std::sort(&sc[0], &sc[m] + 1, cmpj);
        for (register uint i(1); i <= m; ++i) {
            if (sr[i].j > 0)     s[sr[i].id].cv = s[sr[i].id].cv || get(sr[i].i, sr[i].j - 1);
            if (sr[i].j < n * 2) s[sr[i].id].cv = s[sr[i].id].cv || get(sr[i].i, sr[i].j + 1);
        }
        for (register uint i(0); i <= m; ++i)
            ans += (i == m || sc[i].j != sc[i + 1].j) && s[sc[i].id].cv;
        printf("%u\n", ans);
    }
}

signed int main() { Main::main(); return 0; }