题解：P11329 [NOISG 2022 Finals] Towers

· · 题解

一开始我们把每一列的最高点和最低点都选上。然后考虑所有有至少三个点被选取的行，那么这一行只有最左边和最右边需要保留，中间的所有点都可以向上或者向下移动（因为中间的那些点一定是某列的最高点或者最低点）。如此迭代直到没有非法的行即可。具体实现请看代码注释。

时间复杂度：ins 和 del 函数因为依赖于 set，复杂度都是 O(\log N)。然后注意到每个点至多被 ins 一次再 del 一次，因为每一列选取的范围都是不断严格缩小的，所以总体的时间复杂度应该是 O(N \log N)。前面还有一个对点进行排序的步骤，复杂度一样。

#include <bits/stdc++.h>
#define L(i, j, k) for (int i = (j); i <= (k); ++i)
#define R(i, j, k) for (int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int)(a).size())
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 7, V = 1e6;
int n, x[N], y[N], l[N], r[N];
vi vx[N];
bool vis[N];
set<int> st[N];
queue<int> q;
void ins(int i)
{
    // st[t]是纵坐标为t的行中所有选取的点的横坐标
    st[y[i]].insert(x[i]), vis[i] = true;
    // q里面是所有有问题的行的纵坐标
    if (sz(st[y[i]]) > 2)
        q.push(y[i]);
}
void del(int i)
{
    // 删掉所选取的点
    st[y[i]].erase(x[i]), vis[i] = false;
}
int main()
{
    ios ::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    L(i, 1, n)
        // x[i] y[i] 编号为i的点的横纵坐标
        cin >> x[i] >> y[i],
        vx[x[i]].emplace_back(i); // vx[t]: 横坐标为t的列的所有点的编号
    L(i, 1, V) if (sz(vx[i]))
    {
        // 对于所有非空列, 把点按纵坐标排序
        sort(vx[i].begin(), vx[i].end(), [&](int u, int v)
             { return y[u] < y[v]; });
        // 每个列一开始选两个点, 记为高点和低点
        // l[i] 是横坐标为i的列所选取的低点在vx[i]中的编号
        // r[i] 是横坐标为i的列所选取的高点在vx[i]中的编号
        l[i] = 0, r[i] = sz(vx[i]) - 1;
        // 记录选取
        ins(vx[i][l[i]]);
        // 如果这个列只有一个点, 就不用再加一次
        if (l[i] != r[i])
            ins(vx[i][r[i]]);
    }
    while (!q.empty())
    {
        // 正在处理纵坐标是i的行
        int i = q.front();
        q.pop();
        if (sz(st[i]) <= 2)
            continue;
        // mn 这行选取了的最左边的点的横坐标, mx 这行选取了的最右边的点的横坐标
        int mn = *st[i].begin(), mx = *--st[i].end();
        vi vc; // 记录这行里面选取了的但已经被覆盖了点的横坐标
        for (const int &t : st[i])
            if (t != mn && t != mx)
                vc.emplace_back(t);
        for (const int &u : vc) // 遍历所有选取了的但已经被覆盖了的点的横坐标u
        {
            // 注意u这一列里面, 这个被覆盖了的点一定是我们选的高点或者低点
            // 因为我们选的所有点都是某一列的高点或者低点

            // 如果这一列只剩下一个点了, 直接删掉
            if (l[u] == r[u])
            {
                del(vx[u][l[u]]);
                ++l[u];
            }

            // 如果这个被覆盖了的点是我们选的低点
            else if (y[vx[u][l[u]]] == i)
            {
                // 删掉这个低点, 往上移一格, 把新的低点加进来
                del(vx[u][l[u]]), ++l[u], ins(vx[u][l[u]]);
            }

            // 如果这个被覆盖了点是我们选的高点
            else if (y[vx[u][r[u]]] == i)
            {
                // 删掉这个高点, 往下移一格, 把新的高点加进来
                del(vx[u][r[u]]), --r[u], ins(vx[u][r[u]]);
            }

            // 否则这情况是不可能的
            else
            {
                assert(false);
            }

            // 注意我们只会向上或者向下移动, 所以每列自始至终都只有至多两个点, 并且永远都被覆盖
        }
    }
    L(i, 1, n)
        cout << vis[i];
    cout << '\n';
    return 0;
}

（声明：代码来源于网络，注释为本人所加。）