P4169 [Violet] 天使玩偶/SJY摆棋子の题解

#ifndef ONLINE_JUDGE
#pragma GCC optimize("O2", "O3", "Ofast", "inline")
#endif
#include <bits/stdc++.h>
using namespace std;

using it2 = array<int, 2>;

struct p0
{
    it2 x;
    p0(const it2 &y = {0, 0}) : x(y) {}
    bool operator<(const p0 &rhs) const { return x[0] + x[1] < rhs.x[0] + rhs.x[1]; }
    bool operator<=(const p0 &rhs) const { return x[0] + x[1] <= rhs.x[0] + rhs.x[1]; }
};
struct p1
{
    it2 x;
    p1(const it2 &y = {0, 0}) : x(y) {}
    bool operator<(const p1 &rhs) const { return x[0] - x[1] < rhs.x[0] - rhs.x[1]; }
    bool operator<=(const p1 &rhs) const { return x[0] - x[1] <= rhs.x[0] - rhs.x[1]; }
};
struct p2
{
    it2 x;
    p2(const it2 &y = {0, 0}) : x(y) {}
    bool operator<(const p2 &rhs) const { return x < rhs.x; }
    bool operator<=(const p2 &rhs) const { return x < rhs.x; }
};

template <typename Tp, size_t _B = 1536>
struct sortedvector
{
    using vecTp = vector<Tp>;
    using posTp = pair<size_t, size_t>;
    constexpr size_t B() { return _B; }
    size_t siz, bcnt;
    vector<vecTp> vecs;
    sortedvector() : siz(0ULL), bcnt(0ULL) {}
    sortedvector(const vecTp &vec) : siz(vec.size()), bcnt(0ULL)
    {
        vecTp *it = nullptr;
        for (size_t i = 0ULL; i < siz; ++i)
        {
            if (i % B() == 0)
            {
                vecs.emplace_back(vecTp());
                it = &vecs.at(bcnt++);
                it->reserve(B());
            }
            it->emplace_back(vec.at(i));
        }
    }
    posTp begin() const { return {0ULL, 0ULL}; }
    posTp end() const { return {bcnt, 0ULL}; }
    posTp next(const posTp &pos) const
    {
        if (pos.second + 1 == vecs[pos.first].size())
        {
            return {pos.first + 1, 0ULL};
        }
        else
        {
            return {pos.first, pos.second + 1};
        }
    }
    posTp prev(const posTp &pos) const
    {
        if (pos.second == 0ULL)
        {
            return {pos.first - 1, vecs[pos.first - 1].size() - 1ULL};
        }
        else
        {
            return {pos.first, pos.second - 1};
        }
    }
    posTp lower_bound(const Tp &val) const
    {
        for (size_t i = 0ULL; i < bcnt; ++i)
        {
            if (val <= vecs.at(i).back())
            {
                return {i, std::lower_bound(vecs[i].begin(), vecs[i].end(), val) - vecs[i].begin()};
            }
        }
        return {bcnt, 0ULL};
    }
    void insert(const Tp &val)
    {
        posTp pos = lower_bound(val);
        vecTp &vec = vecs.at(pos.first);
        vec.emplace(vec.begin() + pos.second, val);
        ++siz;
        if (vec.size() > B() << 1)
        {
            vecTp half(vec.begin() + B(), vec.end());
            vec.erase(vec.begin() + B(), vec.end());
            vecs.emplace(vecs.begin() + pos.first + 1, half);
            ++bcnt;
        }
    }
    size_t size() const { return siz; }
    Tp &operator[](posTp i) { return vecs.at(i.first).at(i.second); }
    const Tp &operator[](posTp i) const { return vecs.at(i.first).at(i.second); }
};

#define printf __builtin_printf
#ifdef ONLINE_JUDGE
#define getchar getchar_unlocked
#else
#define getchar _getchar_nolock
#endif
#define rd read()
int read()
{
    int ch = 0, res = 0;
    while (!isdigit(ch))
    {
        ch = getchar();
    }
    while (isdigit(ch))
    {
        res = res * 10 + ch - '0', ch = getchar();
    }
    return res;
}

int n, m, t;
vector<it2> a;

signed main()
{
    n = rd, m = rd, a.resize(n);
    for (int i = 0; i < n; ++i)
    {
        a[i] = {rd, rd};
    }
    n += 4;
    a.push_back({0x114514, 0x114514});
    a.push_back({-0x114514, 0x114514});
    a.push_back({-0x114514, -0x114514});
    a.push_back({0x114514, -0x114514});

    vector<p0> tmp0(n);
    for (int i = 0; i < n; ++i)
    {
        tmp0[i] = p0(a[i]);
    }
    sort(tmp0.begin(), tmp0.end());
    sortedvector<p0> a0(tmp0);
    vector<p1> tmp1(n);
    for (int i = 0; i < n; ++i)
    {
        tmp1[i] = p1(a[i]);
    }
    sort(tmp1.begin(), tmp1.end());
    sortedvector<p1> a1(tmp1);
    vector<p2> tmp2(n);
    for (int i = 0; i < n; ++i)
    {
        tmp2[i] = p2(a[i]);
    }
    sort(tmp2.begin(), tmp2.end());
    sortedvector<p2> a2(tmp2);

    int op;
    it2 x;
    while (m--)
    {
        op = rd, x = {rd, rd};
        if (op == 1)
        {
            ++n;
            a0.insert(p0(x));
            a1.insert(p1(x));
            a2.insert(p2(x));
        }
        else
        {
            int res = 0x114514;
            {
                auto p = a0.lower_bound(x);
                {
                    int cnt = 1200;
                    for (auto it = p; it != a0.begin() && cnt; it = a0.prev(it), --cnt)
                    {
                        res = min(res, abs(a0[it].x[0] - x[0]) + abs(a0[it].x[1] - x[1]));
                    }
                }
                {
                    int cnt = 1200;
                    for (auto it = p; it != a0.end() && cnt; it = a0.next(it), --cnt)
                    {
                        res = min(res, abs(a0[it].x[0] - x[0]) + abs(a0[it].x[1] - x[1]));
                    }
                }
            }
            {
                auto p = a1.lower_bound(x);
                {
                    int cnt = 1200;
                    for (auto it = p; it != a1.begin() && cnt; it = a1.prev(it), --cnt)
                    {
                        res = min(res, abs(a1[it].x[0] - x[0]) + abs(a1[it].x[1] - x[1]));
                    }
                }
                {
                    int cnt = 1200;
                    for (auto it = p; it != a1.end() && cnt; it = a1.next(it), --cnt)
                    {
                        res = min(res, abs(a1[it].x[0] - x[0]) + abs(a1[it].x[1] - x[1]));
                    }
                }
            }
            {
                auto p = a2.lower_bound(x);
                {
                    int cnt = 1200;
                    for (auto it = p; it != a2.begin() && cnt; it = a2.prev(it), --cnt)
                    {
                        res = min(res, abs(a2[it].x[0] - x[0]) + abs(a2[it].x[1] - x[1]));
                    }
                }
                {
                    int cnt = 1200;
                    for (auto it = p; it != a2.end() && cnt; it = a2.next(it), --cnt)
                    {
                        res = min(res, abs(a2[it].x[0] - x[0]) + abs(a2[it].x[1] - x[1]));
                    }
                }
            }
            printf("%d\n", res);
        }
    }

    return 0;
}