#创作计划# K-D Tree 入门 2

一些应用

P3769 [CH弱省胡策R2] TATT

原问题求解的是四维意义下的 LIS，容易想到先按第一维排序，然后转化为三维的偏序关系。

比较常规的解法是 cdq 分治套 cdq 分治优化 dp，但是这里采用 KD-Tree 来优化她。

按照第一维排序后，设 $f_i$ 表示当前以 $i$ 点为结尾的 LIS 长度最长是多少。有初始状态 $f_i=1$，转移方程形如：

$$f_i=(\max\limits_{x_j\le x_i,y_j\le y_i,z_j\le z_i}f_j)+1$$

考虑用数据结构优化。容易想到写一个树套树。注意到前面部分的查询其实就是在一个三维空间中查询最大值，然后添加 $i$ 位置就是在 KD-Tree 上单点插入。在每个结点上维护子树最大值信息，可以做到 $O(n^{5/3})$ 解决该问题。

看上去比较吓人，但是 $n$ 只有 $50000$，而且 KDT 的时间复杂度跑不满，所以仍然可以无压力通过。

// Author: 美丽好 rua 的大宋宋

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <iostream>
#include <string.h>
#include <bits/stl_algo.h>
#define int long long
using namespace std;
const int N = 300010;
const int inf = 1e18;
const int mod = 998244353;

inline int power(int a, int b, int c)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % c;
        a = a * a % c, b >>= 1;
    }
    return ans;
}

inline int inversion(int x) { return power(x, mod - 2, mod); }

using ull = unsigned long long;
using i128 = __int128;

const int dim = 3;
int m, lx[3], rx[3];
struct Node
{
    int x[3], val, mx, l, r, L[3], R[3];
} tree[N];

int dest[N], root[20], cnt, idx;

inline void pushup(int rt)
{
    tree[rt].mx = max({tree[rt].val, tree[tree[rt].l].mx, tree[tree[rt].r].mx});
    for (int i = 0; i < dim; ++i)
    {
        tree[rt].L[i] = tree[rt].R[i] = tree[rt].x[i];
        if (tree[rt].l)
        {
            tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].l].L[i]);
            tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].l].R[i]);
        }
        if (tree[rt].r)
        {
            tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].r].L[i]);
            tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].r].R[i]);
        }
    }
}

inline int build(int l, int r, int dim_op)
{
    int mid = l + r >> 1;
    nth_element(dest + l, dest + mid, dest + r + 1, [&](auto &l, auto &r)
    {
        return tree[l].x[dim_op] < tree[r].x[dim_op];
    });
    tree[dest[mid]].l = tree[dest[mid]].r = 0;
    if (l < mid)
        tree[dest[mid]].l = build(l, mid - 1, (dim_op + 1) % dim);
    if (mid < r)
        tree[dest[mid]].r = build(mid + 1, r, (dim_op + 1) % dim);
    pushup(dest[mid]);
    return dest[mid];
}

inline void push_cache(int &rt)
{
    if (!rt)
        return;
    if (tree[rt].l)
        push_cache(tree[rt].l);
    dest[++cnt] = rt;
    if (tree[rt].r)
        push_cache(tree[rt].r);
    rt = 0;
}

inline int luminescent(int rt)
{
    if (!rt)
        return 0;
    int ok = 1;
    for (int i = 0; i < dim; ++i)
        if (lx[i] <= tree[rt].L[i] && tree[rt].R[i] <= rx[i])
            ;
        else
        {
            ok = 0;
            break;
        }
    if (ok)
        return tree[rt].mx;
    for (int i = 0; i < dim; ++i)
        if (tree[rt].R[i] < lx[i] || rx[i] < tree[rt].L[i])
            return 0;
    ok = 1;
    for (int i = 0; i < dim; ++i)
        if (!(lx[i] <= tree[rt].x[i] && tree[rt].x[i] <= rx[i]))
        {
            ok = 0;
            break;
        }
    if (ok)
        return max({luminescent(tree[rt].l), luminescent(tree[rt].r), tree[rt].val});
    return max(luminescent(tree[rt].l), luminescent(tree[rt].r));
}

inline void ins(int x[3], int val)
{
    ++idx;
    for (int i = 0; i < dim; ++i)
        tree[idx].x[i] = x[i];
    tree[idx].val = val;
    dest[cnt = 1] = idx;
    for (int i = 0; ; ++i)
        if (!root[i])
        {
            root[i] = build(1, cnt, 0);
            break;
        }
        else
            push_cache(root[i]);
}

inline int qry(int _lx[3], int _rx[3])
{
    for (int i = 0; i < 3; ++i)
        lx[i] = _lx[i], rx[i] = _rx[i];
    int mx = 0;
    for (int i = 0; i < 20; ++i)
        if (root[i])
            mx = max(mx, luminescent(root[i]));
    return mx;
}

struct Point
{
    int x, y, z, w;
} pnt[N];
int f[N];

signed main()
{
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    cin.tie(0)->sync_with_stdio(false);
    cin >> m;
    for (int i = 1; i <= m; ++i)
        cin >> pnt[i].x >> pnt[i].y >> pnt[i].z >> pnt[i].w;
    sort(pnt + 1, pnt + m + 1, [&](auto &l, auto &r) { return make_tuple(l.x, l.y, l.z, l.w) < make_tuple(r.x, r.y, r.z, r.w); });
    for (int i = 1; i <= m; ++i)
        f[i] = 1;
    int mx = 0;
    for (int i = 1; i <= m; ++i)
    {
        int x[3] = {pnt[i].y, pnt[i].z, pnt[i].w};
        int _[3] = {(int)-1e9, (int)-1e9, (int)-1e9};
        int val = qry(_, x) + 1;
        mx = max(mx, val);
        ins(x, val);
    }
    cout << mx << '\n';
    return 0;
}

P5621 [DBOI2019] 德丽莎世界第一可爱

在上个题的基础上加了一个点的权值，只需要把上一题的 dp 初始条件修改为 $f_i=C_i$，转移方程修改为：

$$f_i=(\max\limits_{E_j\le E_i,A_j\le A_i,D_j\le D_i}f_j)+1$$

按照 $H$ 从小到大排序转移即可，需要大力卡常才能过。

// Author: 美丽好 rua 的大宋宋

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
const int dim = 3;
const int MAXL = 16;

#if defined(__GNUC__)
#define LIKELY(x) (__builtin_expect(!!(x), 1))
#define UNLIKELY(x) (__builtin_expect(!!(x), 0))
#define HOT __attribute__((hot))
#else
#define LIKELY(x) (x)
#define UNLIKELY(x) (x)
#define HOT
#endif

int m, lx[3], rx[3];

struct Node
{
    int x[3], l, r, L[3], R[3];
    long long val, mx;
} tree[N];

int dest[N], root[MAXL], cnt, idx;

static int OP = 0;
static const int nxt[3] = {1, 2, 0};

static bool cmp_idx(const int &a, const int &b)
{
    return tree[a].x[OP] < tree[b].x[OP];
}

inline void pushup(int rt)
{
    Node &t = tree[rt];
    const int l = t.l, r = t.r;

    long long mx0 = t.val;
    if (l)
    {
        long long v = tree[l].mx;
        if (v > mx0)
            mx0 = v;
    }
    if (r)
    {
        long long v = tree[r].mx;
        if (v > mx0)
            mx0 = v;
    }
    t.mx = mx0;
    if (t.mx < 0)
        t.mx = 0;

    int L0 = t.x[0], R0 = L0;
    if (l)
    {
        if (tree[l].L[0] < L0)
            L0 = tree[l].L[0];
        if (tree[l].R[0] > R0)
            R0 = tree[l].R[0];
    }
    if (r)
    {
        if (tree[r].L[0] < L0)
            L0 = tree[r].L[0];
        if (tree[r].R[0] > R0)
            R0 = tree[r].R[0];
    }
    t.L[0] = L0;
    t.R[0] = R0;

    int L1 = t.x[1], R1 = L1;
    if (l)
    {
        if (tree[l].L[1] < L1)
            L1 = tree[l].L[1];
        if (tree[l].R[1] > R1)
            R1 = tree[l].R[1];
    }
    if (r)
    {
        if (tree[r].L[1] < L1)
            L1 = tree[r].L[1];
        if (tree[r].R[1] > R1)
            R1 = tree[r].R[1];
    }
    t.L[1] = L1;
    t.R[1] = R1;

    int L2 = t.x[2], R2 = L2;
    if (l)
    {
        if (tree[l].L[2] < L2)
            L2 = tree[l].L[2];
        if (tree[l].R[2] > R2)
            R2 = tree[l].R[2];
    }
    if (r)
    {
        if (tree[r].L[2] < L2)
            L2 = tree[r].L[2];
        if (tree[r].R[2] > R2)
            R2 = tree[r].R[2];
    }
    t.L[2] = L2;
    t.R[2] = R2;
}

inline int build(int l, int r, int op)
{
    int mid = (l + r) >> 1;
    OP = op;
    nth_element(dest + l, dest + mid, dest + r + 1, cmp_idx);
    int rt = dest[mid];
    tree[rt].l = tree[rt].r = 0;
    if (l < mid)
        tree[rt].l = build(l, mid - 1, nxt[op]);
    if (mid < r)
        tree[rt].r = build(mid + 1, r, nxt[op]);
    pushup(rt);
    return rt;
}

inline void push_cache(int &rt)
{
    if (!rt)
        return;
    if (tree[rt].l)
        push_cache(tree[rt].l);
    dest[++cnt] = rt;
    if (tree[rt].r)
        push_cache(tree[rt].r);
    rt = 0;
}

HOT inline void luminescent(int rt, long long &best)
{
    if (UNLIKELY(!rt))
        return;
    if (tree[rt].mx <= best)
        return;

    Node &t = tree[rt];

    if (t.R[0] < lx[0] || rx[0] < t.L[0] ||
        t.R[1] < lx[1] || rx[1] < t.L[1] ||
        t.R[2] < lx[2] || rx[2] < t.L[2])
        return;

    if (lx[0] <= t.L[0] && t.R[0] <= rx[0] &&
        lx[1] <= t.L[1] && t.R[1] <= rx[1] &&
        lx[2] <= t.L[2] && t.R[2] <= rx[2])
    {
        if (t.mx > best)
            best = t.mx;
        return;
    }

    if (lx[0] <= t.x[0] && t.x[0] <= rx[0] &&
        lx[1] <= t.x[1] && t.x[1] <= rx[1] &&
        lx[2] <= t.x[2] && t.x[2] <= rx[2])
    {
        if (t.val > best)
            best = t.val;
    }

    const int lc = t.l, rc = t.r;

#if defined(__GNUC__)
    if (lc)
        __builtin_prefetch(&tree[lc], 0, 1);
    if (rc)
        __builtin_prefetch(&tree[rc], 0, 1);
#endif

    int first = lc, second = rc;
    if (rc && (!lc || tree[rc].mx > tree[lc].mx))
    {
        first = rc;
        second = lc;
    }

    if (first && tree[first].mx > best)
        luminescent(first, best);
    if (second && tree[second].mx > best)
        luminescent(second, best);
}

inline void ins(int x[3], long long val)
{
    ++idx;
    tree[idx].x[0] = x[0];
    tree[idx].x[1] = x[1];
    tree[idx].x[2] = x[2];
    tree[idx].val = val;
    dest[cnt = 1] = idx;

    // MAXL 循环展开（0..15）
    if (!root[0])
    {
        root[0] = build(1, cnt, 0);
        return;
    }
    push_cache(root[0]);
    if (!root[1])
    {
        root[1] = build(1, cnt, 0);
        return;
    }
    push_cache(root[1]);
    if (!root[2])
    {
        root[2] = build(1, cnt, 0);
        return;
    }
    push_cache(root[2]);
    if (!root[3])
    {
        root[3] = build(1, cnt, 0);
        return;
    }
    push_cache(root[3]);
    if (!root[4])
    {
        root[4] = build(1, cnt, 0);
        return;
    }
    push_cache(root[4]);
    if (!root[5])
    {
        root[5] = build(1, cnt, 0);
        return;
    }
    push_cache(root[5]);
    if (!root[6])
    {
        root[6] = build(1, cnt, 0);
        return;
    }
    push_cache(root[6]);
    if (!root[7])
    {
        root[7] = build(1, cnt, 0);
        return;
    }
    push_cache(root[7]);
    if (!root[8])
    {
        root[8] = build(1, cnt, 0);
        return;
    }
    push_cache(root[8]);
    if (!root[9])
    {
        root[9] = build(1, cnt, 0);
        return;
    }
    push_cache(root[9]);
    if (!root[10])
    {
        root[10] = build(1, cnt, 0);
        return;
    }
    push_cache(root[10]);
    if (!root[11])
    {
        root[11] = build(1, cnt, 0);
        return;
    }
    push_cache(root[11]);
    if (!root[12])
    {
        root[12] = build(1, cnt, 0);
        return;
    }
    push_cache(root[12]);
    if (!root[13])
    {
        root[13] = build(1, cnt, 0);
        return;
    }
    push_cache(root[13]);
    if (!root[14])
    {
        root[14] = build(1, cnt, 0);
        return;
    }
    push_cache(root[14]);
    if (!root[15])
    {
        root[15] = build(1, cnt, 0);
        return;
    }
    push_cache(root[15]);
    root[MAXL - 1] = build(1, cnt, 0);
}

inline long long qry(int _lx[3], int _rx[3])
{
    lx[0] = _lx[0];
    lx[1] = _lx[1];
    lx[2] = _lx[2];
    rx[0] = _rx[0];
    rx[1] = _rx[1];
    rx[2] = _rx[2];
    long long best = 0;

    // MAXL 循环展开（0..15）
    {
        int rt = root[0];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[1];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[2];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[3];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[4];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[5];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[6];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[7];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[8];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[9];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[10];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[11];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[12];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[13];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[14];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }
    {
        int rt = root[15];
        if (rt)
        {
            if (tree[rt].mx > best)
            {
                Node &t = tree[rt];
                if (!(t.R[0] < lx[0] || rx[0] < t.L[0] || t.R[1] < lx[1] || rx[1] < t.L[1] || t.R[2] < lx[2] || rx[2] < t.L[2]))
                    luminescent(rt, best);
            }
        }
    }

    return best;
}

struct Point
{
    int x, y, z, w, cost;
} pnt[N];

static bool cmp(const Point &a, const Point &b)
{
    if (a.x != b.x)
        return a.x < b.x;
    if (a.y != b.y)
        return a.y < b.y;
    if (a.z != b.z)
        return a.z < b.z;
    return a.w < b.w;
}

static char buf[1000010];
static char *p1 = buf, *p2 = buf;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++)
static int read()
{
    int x = 0, op = 1, c = gc();
    while (c < 48)
    {
        if (c == '-')
            op = -1;
        c = gc();
    }
    while (c > 47)
    {
        x = (x << 3) + (x << 1) + (c & 15);
        c = gc();
    }
    return x * op;
}

int main()
{
    m = read();
    for (int i = 1; i <= m; ++i)
        pnt[i].x = read(), pnt[i].y = read(), pnt[i].z = read(),
        pnt[i].w = read(), pnt[i].cost = read();

    sort(pnt + 1, pnt + m + 1, cmp);

    long long ans = LLONG_MIN;
    for (int i = 1; i <= m; ++i)
    {
        int x3[3] = {pnt[i].y, pnt[i].z, pnt[i].w};
        int lo[3] = {INT_MIN, INT_MIN, INT_MIN};
        long long best = qry(lo, x3) + pnt[i].cost;
        if (best > ans)
            ans = best;
        ins(x3, best);
    }
    cout << ans << '\n';
    return 0;
}

P4848 崂山白花蛇草水

问题可以转化为矩形查询第 $k$ 大值，矩形加。

看到查询第 $k$ 大值容易想到用动态开点值域线段树维护，但是问题是在一个平面上的，也就是说普通的动态开点值域线段树已经无法维护。

因此容易想到树套树，即在动态开点值域线段树的每个结点上，都维护一个 K-D Tree。具体而言：

• 矩形加是简单的。
• 矩形查第 $k$ 大可以在动态开点值域线段树上二分，对于当前值域线段树上的点 $u$，若其右儿子 $r$ 对应的 K-D Tree 上当前矩形有 $k$ 个点，那么就递归右子树，否则就递归左子树。

外层的动态开点值域线段树时间复杂度为 $O(\log V)$，内侧的 K-D Tree 时间复杂度为 $O(n^{\frac12})$，因此总时间复杂度为 $O(n^{\frac32}\log V)$。

下面这份代码曾经可以通过，找个时间再来卡常（）

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
// #define int long long
using namespace std;
int n, q;
const int N = 500010;
// const int N = 5010;
namespace KDT
{
    struct Node
    {
        int L[2], R[2], x[2], l, r;
        int val, sum;
        // Node()
        // {
        //     memset(L, 0, sizeof L);
        //     memset(R, 0, sizeof R);
        //     memset(x, 0, sizeof x);
        //     l = r = val = sum = 0;
        // }
    } tree[N * 4 * 20];
    void pushup(int rt)
    {
        for (int i = 0; i < 2; ++i)
        {
            tree[rt].L[i] = tree[rt].R[i] = tree[rt].x[i];
            if (tree[rt].l)
            {
                tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].l].L[i]);
                tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].l].R[i]);
            }
            if (tree[rt].r)
            {
                tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].r].L[i]);
                tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].r].R[i]);
            }
        }
        tree[rt].sum = tree[tree[rt].l].sum + 1 + tree[tree[rt].r].sum;
    }
    int idx = 0, top = 0, dest[N * 4 * 20];
    void push_cache(int &root)
    {
        if (!root)
            return;
        dest[++top] = root;
        push_cache(tree[root].l);
        push_cache(tree[root].r);
        root = 0;
    }
    int build(int l, int r, int op = 0)
    {
        int mid = l + r >> 1;
        nth_element(dest + l, dest + mid, dest + r + 1, [&](auto &l, auto &r)
        {
            return tree[l].x[op] < tree[r].x[op];
        });
        int x = dest[mid];
        if (l < mid)
            tree[x].l = build(l, mid - 1, op ^ 1);
        if (mid < r)
            tree[x].r = build(mid + 1, r, op ^ 1);
        pushup(x);
        return x;
    }
    void loyalty(int *root, int x, int y)
    {
        ++idx;
        // cout << "idx = " << idx << '\n';
        tree[idx].x[0] = x;
        tree[idx].x[1] = y;
        assert(x > 0 && y > 0);
        dest[top = 1] = idx;
        for (int i = 0; i < 20; ++i)
        {
            if (!root[i])
            {
                root[i] = build(1, top, 0);
                // cout << "BUILD! " << i << ' ' << root[i] << '\n';
                return;
            }
            push_cache(root[i]);
            assert(i != 19);
        }
    }
    int luminescent(int root, int x1, int y1, int x2, int y2)
    {
        const int x[] = {x1, y1}, y[] = {x2, y2};
        int ok = 0;
        for (int i = 0; i < 2; ++i)
            if (x[i] <= tree[root].L[i] && tree[root].R[i] <= y[i])
                ;
            else
            {
                ok = 1;
                break;
            }
        if (!ok)
            return tree[root].sum;
        for (int i = 0; i < 2; ++i)
            if (tree[root].R[i] < x[i] || y[i] < tree[root].L[i])
            {
                // cout << i << ")) " << x[i] << ' ' << y[i] << ' ' << tree[root].x[i] << ' ' << tree[root].x[i] << '\n';
                return 0;
            }
        ok = 1;
        for (int i = 0; i < 2; ++i)
            if (!(x[i] <= tree[root].x[i] && tree[root].x[i] <= y[i]))
            {
                ok = 0;
                break;
            }
        return luminescent(tree[root].l, x1, y1, x2, y2) + luminescent(tree[root].r, x1, y1, x2, y2) + ok;
    }
}
namespace SegmentTree
{
    int idx = 1;
    struct Node
    {
        int l, r, root[20];
        // Node()
        // {
        //     l = r = 0;
        //     memset(root, 0, sizeof root);
        // }
        // void init(int p)
        // {
        //     l = r = p;
        //     memset(root, 0, sizeof root);
        // }
    } tree[N << 5];
    void loyalty(int l, int r, int rt, int x, int y, int val)
    {
        // if (l > 5e7) throw;
        KDT::loyalty(tree[rt].root, x, y);
        if (l == r)
            return;
        // cout << "Mod " << tree[rt].root[0] << ' ' << x << ' ' << y << ' ' << val << '\n';
        int mid = l + r >> 1;
        if (val <= mid)
        {
            if (!tree[rt].l)
                tree[rt].l = ++idx;
            loyalty(l, mid, tree[rt].l, x, y, val);
        }
        else
        {
            if (!tree[rt].r)
                tree[rt].r = ++idx;
            loyalty(mid + 1, r, tree[rt].r, x, y, val);
        }
    }
    int luminescent(int l, int r, int rt, int x1, int y1, int x2, int y2, int k)
    {
        // cout << "luminescent: " << l << ' ' << r << ' ' << rt << ' ' << tree[rt].root[0] << '\n';
        if (!rt)
            return 0;
        if (l == r)
        {
            int s = 0;
            // cout << "aucadsf\n";
            for (int i = 0; i < 20; ++i)
            {
                // cout << "mpadfad " << i << ": " << tree[rt].root[i] << '\n';
                // if (tree[rt].root[i])
                //     cout << "wa " << tree[rt].root[i] << ' ' << KDT::tree[1].sum << ' ' << KDT::tree[1].x[0] << ' ' << KDT::tree[1].x[1] << ' ' << KDT::tree[2].x[0] << ' ' << KDT::tree[2].x[1] << ' ' << KDT::tree[3].x[0] << ' ' << KDT::tree[3].x[1] << ' ' << KDT::tree[4].x[0] << ' ' << KDT::tree[4].x[1] << '\n';
                s += KDT::luminescent(tree[rt].root[i], x1, y1, x2, y2);
            }
            if (s >= k)
                return l;
            return 0;
            // return l;
        }
        int mid = l + r >> 1, s = 0;
        if (tree[rt].r)
            for (int i = 0; i < 20; ++i)
            {
                // cout << "njb: " << i << ' ' << tree[rt].r << ' ' << tree[tree[rt].r].root[i] << '\n';
                s += KDT::luminescent(tree[tree[rt].r].root[i], x1, y1, x2, y2);
            }
        // assert(!s);
        // cout << "yueqr " << l << ' ' << r << ' ' << rt << ' ' << s << ' ' << k << '\n';
        if (s >= k)
            return luminescent(mid + 1, r, tree[rt].r, x1, y1, x2, y2, k);
        return luminescent(l, mid, tree[rt].l, x1, y1, x2, y2, k - s);
    }
}
signed main()
{
    // freopen("niji", "w", stdout);
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> q;
    int la = 0;
    while (q--)
    {
        int o;
        cin >> o;
        if (o == 1)
        {
            int x, y, v;
            cin >> x >> y >> v;
            x ^= la, y ^= la, v ^= la;
            SegmentTree::loyalty(1, 1e9, 1, x, y, v);
        }
        else
        {
            int x1, y1, x2, y2, k;
            cin >> x1 >> y1 >> x2 >> y2 >> k;
            x1 ^= la, y1 ^= la, x2 ^= la, y2 ^= la, k ^= la;
            int res = SegmentTree::luminescent(1, 1e9, 1, x1, y1, x2, y2, k);
            cout << ((la = res) ? to_string(res) : "NAIVE!ORZzyz.") << '\n';
        }
    }
    return 0;
}

P5471 [NOI2019] 弹跳

题意比较复杂，这里 copy 出一个简要题意：

给出二维平面上的 $n$ 个整点 $(x_i,y_i)$，满足 $1\le x_i\le w,1\le y_i\le h$。按给出顺序编号为 $1,2,\ldots,n$。有 $m$ 次连边操作，每次操作给定 $p,t,L,R,D,U$，从结点 $p$ 到满足条件 $L\le x_i\le R,D\le y_i\le U$ 的所有这样的结点 $i$ 连接一条边权为 $t$ 的有向边。求在所有连边操作结束后，从编号为 $1$ 的点到其他点的最短路长度。

Data Range: $1\le w,h\le n\le 70000,1\le m\le 150000,1\le t_i\le 10000$

题解：

先考虑一维的情况，此时连边操作形如让一个点 $p$ 向一段区间 $[l,r]$ 连边，容易发现这就是【模板】线段树优化建图。

扩展到二维，容易想到用 K-D Tree 来优化建图。具体的：

• 建立由这 $n$ 个点组成的 K-D Tree，该树上有 $n$ 个结点，令这些点对应过来的编号为 $n+1,n+2,\ldots,2n$ 号。
• 对于一个点 $p$ 向一个平面内所有点连边的情况，考虑直接遍历整棵 K-D Tree，对于当前所遍历到的结点 $u$ 而言：
  • 若 $u$ 点子树对应的平面和查询的平面无交，那么不再递归，直接返回。
  • 若 $u$ 点子树对应的平面是查询平面的子集，那么直接从 $p$ 点向 $u+n$ 点连一条边权为 $t$ 的有向边即可。
  • 对于其余情况，特判掉 $u$ 点自身所对应的坐标在查询平面内的情况，然后直接向左右子树暴力递归即可。
• 最后对于每个 $i=1\ldots n$，由 $i+n$ 点向 $i$ 点连一条边权为 $0$ 的有向边即可。

由 K-D Tree 的时间复杂度证明可知，这种方式建图会连 $O(m\sqrt n)$ 条边。因为 $n\le 70000$，所以该建边方法是可行的。此时如果直接显式建图，大约需要建 $4\times 10^7$ 条边，会爆内存。将上述做法改为隐式建图即可通过。

注：spfa 被卡了。

P12065 [THOI 2012] 森林旅店

邻域查询板子题，把前面的 P2093 和 P4148 合起来就可以过。

// #pragma GCC optimize(3, "Ofast", "inline", "unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ld = long double;
const int N = 1000010;
int n, m, K;
int idx, cnt, dest[N], root[N], lx[2], rx[2];
struct Node
{
    int x[2];
    int L[2], R[2];
    int l, r;
} tree[N];
struct Point
{
    int x[2], id;
} a[N];
void pushup(int rt)
{
    for (int i = 0; i < 2; ++i)
    {
        tree[rt].L[i] = tree[rt].R[i] = tree[rt].x[i];
        if (tree[rt].l)
        {
            tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].l].L[i]);
            tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].l].R[i]);
        }
        if (tree[rt].r)
        {
            tree[rt].L[i] = min(tree[rt].L[i], tree[tree[rt].r].L[i]);
            tree[rt].R[i] = max(tree[rt].R[i], tree[tree[rt].r].R[i]);
        }
    }
}
int build(int l, int r, int op)
{
    int mid = l + r >> 1;
    nth_element(dest + l, dest + mid, dest + r + 1, [&](auto &l, auto &r)
                { return tree[l].x[op] < tree[r].x[op]; });
    if (l < mid)
        tree[dest[mid]].l = build(l, mid - 1, op ^ 1);
    if (mid < r)
        tree[dest[mid]].r = build(mid + 1, r, op ^ 1);
    pushup(dest[mid]);
    return dest[mid];
}
int mx, mi;
priority_queue<pair<ld, int>> q;
inline ld sq(int x)
{
    return x * x;
}
inline ld cb(int x)
{
    return 1. * x * x * x;
}
// inline int expmin(int o, int id)
// {
//     if (!o)
//         return 1e18;
//     return max(0ll, tree[id].x[0] - tree[o].R[0]) + max(0ll, tree[o].L[0] - tree[id].x[0]) + max(0ll, tree[id].x[1] - tree[o].R[1]) + max(0ll, tree[o].L[1] - tree[id].x[1]);
// }
inline ld dist(int x, int y)
{
    if (K == 2)
        return sqrt(sq(tree[x].x[0] - tree[y].x[0]) + sq(tree[x].x[1] - tree[y].x[1]));
    else if (K == 3)
        return cbrt(cb(tree[x].x[0] - tree[y].x[0]) + cb(tree[x].x[1] - tree[y].x[1]));
    return abs(tree[x].x[0] - tree[y].x[0]) + abs(tree[x].x[1] - tree[y].x[1]);
}
inline ld dist(int x, int yx, int yy)
{
    if (K == 2)
        return sqrt(sq(tree[x].x[0] - yx) + sq(tree[x].x[1] - yy));
    else if (K == 3)
        return cbrt(cb(tree[x].x[0] - yx) + cb(tree[x].x[1] - yy));
    return abs(tree[x].x[0] - yx) + abs(tree[x].x[1] - yy);
}
inline ld expmin(int u, int yx, int yy)
{
    ld dx = 0, dy = 0;
    if (yx < tree[u].L[0])
        dx = (ld)(tree[u].L[0] - yx);
    else if (yx > tree[u].R[0])
        dx = (ld)(yx - tree[u].R[0]);
    if (yy < tree[u].L[1])
        dy = (ld)(tree[u].L[1] - yy);
    else if (yy > tree[u].R[1])
        dy = (ld)(yy - tree[u].R[1]);
    if (K == 1)
        return dx + dy;
    if (K == 2)
        return sqrt(dx * dx + dy * dy);
    return cbrt(dx * dx * dx + dy * dy * dy);
}
int px, py, k, x, y, id;
void dfsmin(int rt)
{
    if (!rt)
        return;
    if (q.size() == k && q.top().first <= expmin(rt, x, y))
        return;
    // cerr << "****\n";
    auto oo = q.top();
    if (oo > make_pair(dist(rt, x, y), -a[rt].id))
        q.pop(), q.emplace(dist(rt, x, y), -a[rt].id);
    int d1 = expmin(tree[rt].l, x, y), d2 = expmin(tree[rt].r, x, y);
    if (d1 > d2)
    {
        if (tree[rt].l && d1 <= q.top().first)
            dfsmin(tree[rt].l);
        if (tree[rt].r && d2 <= q.top().first)
            dfsmin(tree[rt].r);
    }
    else
    {
        if (tree[rt].r && d2 <= q.top().first)
            dfsmin(tree[rt].r);
        if (tree[rt].l && d1 <= q.top().first)
            dfsmin(tree[rt].l);
    }
}
inline void push_cache(int &rt)
{
    if (!rt)
        return;
    if (tree[rt].l)
        push_cache(tree[rt].l);
    dest[++cnt] = rt;
    if (tree[rt].r)
        push_cache(tree[rt].r);
    rt = 0;
}
const int inf = 1e18;
// pair{first, second}: dist ;; id
signed main()
{
    cin.tie(0)->sync_with_stdio(false);
    cout << fixed << setprecision(4);
    cin >> n >> m >> K >> k;
    for (int i = 1; i <= n; ++i)
    {
        int x, y;
        cin >> x >> y;
        cnt = 0;
        ++idx;
        tree[idx].x[0] = x;
        tree[idx].x[1] = y;
        dest[++cnt] = idx;
        for (int i = 0;; ++i)
            if (!root[i])
            {
                root[i] = build(1, cnt, 0);
                break;
            }
            else
                push_cache(root[i]);
    }
    int res = 1e18;
    for (int i = 1; i <= m; ++i)
    {
        while (q.size())
            q.pop();
        char o;
        cin >> o;
        if (o == 'Q')
        {
            cin >> px >> py;
            for (int i = 0; i < k; ++i)
                q.emplace(inf, inf);
            x = px, y = py, id = k;
            for (int i = 0; i < 20; ++i)
                if (root[i])
                    dfsmin(root[i]);
            vector<ld> v;
            while (q.size())
                v.emplace_back(q.top().first), q.pop();
            sort(v.begin(), v.end());
            for (ld &x : v)
                cout << x << ' ';
            cout << '\n';
        }
        else
        {
            int x, y;
            cin >> x >> y;
            cnt = 0;
            ++idx;
            tree[idx].x[0] = x;
            tree[idx].x[1] = y;
            dest[++cnt] = idx;
            for (int i = 0;; ++i)
                if (!root[i])
                {
                    root[i] = build(1, cnt, 0);
                    break;
                }
                else
                    push_cache(root[i]);
        }
    }
    return 0;
}