#创作计划# K-D Tree 入门 2
2025-10-31 21:18:28
发布于：山东
78阅读
0回复
0点赞
一些应用
P3769 [CH弱省胡策R2] TATT
原问题求解的是四维意义下的 LIS，容易想到先按第一维排序，然后转化为三维的偏序关系。
比较常规的解法是 cdq 分治套 cdq 分治优化 dp，但是这里采用 KD-Tree 来优化她。
按照第一维排序后，设 表示当前以 点为结尾的 LIS 长度最长是多少。有初始状态 ，转移方程形如：
考虑用数据结构优化。容易想到写一个树套树。注意到前面部分的查询其实就是在一个三维空间中查询最大值，然后添加 位置就是在 KD-Tree 上单点插入。在每个结点上维护子树最大值信息，可以做到 解决该问题。
看上去比较吓人，但是 只有 ，而且 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;
}
在上个题的基础上加了一个点的权值，只需要把上一题的 dp 初始条件修改为 ，转移方程修改为：
按照 从小到大排序转移即可，需要大力卡常才能过。
// 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;
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;
{
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-D Tree。具体而言：
- 矩形加是简单的。
- 矩形查第 大可以在动态开点值域线段树上二分，对于当前值域线段树上的点 ，若其右儿子 对应的 K-D Tree 上当前矩形有 个点，那么就递归右子树，否则就递归左子树。
外层的动态开点值域线段树时间复杂度为 ，内侧的 K-D Tree 时间复杂度为 ，因此总时间复杂度为 。
下面这份代码曾经可以通过，找个时间再来卡常（）
// #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 出一个简要题意：
给出二维平面上的 个整点 ，满足 。按给出顺序编号为 。有 次连边操作，每次操作给定 ，从结点 到满足条件 的所有这样的结点 连接一条边权为 的有向边。求在所有连边操作结束后，从编号为 的点到其他点的最短路长度。
Data Range:
题解：
先考虑一维的情况，此时连边操作形如让一个点 向一段区间 连边，容易发现这就是【模板】线段树优化建图。
扩展到二维，容易想到用 K-D Tree 来优化建图。具体的：
- 建立由这 个点组成的 K-D Tree，该树上有 个结点，令这些点对应过来的编号为 号。
- 对于一个点 向一个平面内所有点连边的情况，考虑直接遍历整棵 K-D Tree，对于当前所遍历到的结点 而言：
- 若 点子树对应的平面和查询的平面无交，那么不再递归，直接返回。
- 若 点子树对应的平面是查询平面的子集，那么直接从 点向 点连一条边权为 的有向边即可。
- 对于其余情况，特判掉 点自身所对应的坐标在查询平面内的情况，然后直接向左右子树暴力递归即可。
- 最后对于每个 ，由 点向 点连一条边权为 的有向边即可。
由 K-D Tree 的时间复杂度证明可知，这种方式建图会连 条边。因为 ，所以该建边方法是可行的。此时如果直接显式建图，大约需要建 条边，会爆内存。将上述做法改为隐式建图即可通过。
注：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;
}
有帮助，赞一个