与 jlf 学长一起出的水题,强制在线的动态三维偏序。
题目大意
维护一个二维点集,每一个点有权值,支持两种操作:
- 加入一个坐标为 (x,y)(x,y)(x,y) 并且权值为 vvv 的点;
- 查询在所有满足 x0≤x≤x1x_0 \le x \le x_1x0≤x≤x1 且 y0≤y≤y1y_0\le y\le y_1y0≤y≤y1 的点中,第 kkk 大的点权是多少。
操作总数为 qqq,强制在线。
1≤x,y≤1051\le x,y\le 10^51≤x,y≤105,1≤v≤1091\le v\le10^91≤v≤109,1≤q≤1051\le q\le10^51≤q≤105。
题目链接
BZOJ 4604(这是不要求强制在线的版本)
命题
这道题的 Idea 一开始是我提出的,题面、标程和数据都是 jlf 学长写的。去年二轮省选之后的一段时间,我当时似乎在学 CDQ 分治,于是接触了很多求各种东西上第 k 大的权值的题目。似乎 BZOJ 3065(带插入区间第 k 小)也是在那个时候A掉的。之后又做了一些 k-d tree 的题目,都是解决平面上问题的。于是就自然的有了一个想法,如果是求带插入平面区域第 k 小呢?然后我首先想了一些解决这个问题的离线算法,整体二分之类的。但是 jlf 前辈认为应该强制在线,并提供了一些使用了 k-d tree 的解法。于是这道题就愉快的诞生了,放到了 BZOJ 上给大家水一水。其实 jlf 似乎没有写权值线段树,于是标程的复杂度其实非常有趣……不要在意这些细节
题面来自于我去年立的一个 flag,进省队就喝白花蛇草水。作为一个立 flag 一定会收的人(,我肯定是喝了白花蛇草水的(参加2016年山东省队集训的同学可能有印象),至于体验如何……可以自己去尝一尝啊斜眼笑
其实这个题目本来是可以叫“视察”的……内容就是 jlf 神犇去二机房视察,然后拿出鸭嘴笔在平面上做微小的贡献……(不过因为我拖延没写完题面 jlf 前辈就写成了这个样,但是无解时输出 NAIVE 是我坚持留下的)
题解
考虑建立一棵权值线段树,查询时在权值线段树上二分。则在权值线段树的每一个节点上,我们要维护一个结构,支持加入一个点与查询一个平面区域内点的数量。显然可以用 k-d tree 来实现这两种操作。但是注意到 k-d tree 不支持旋转操作,需要使用类似替罪羊树的平衡方法,利用重构子树来保持树的平衡。(如果不重构是会被卡的哟)
假设点权 vvv 的最大值为 CCC,则每个加入点的操作需要进行 O(logC)O(\log C)O(logC) 次在 k-d tree 上的插入操作。k-d tree 上插入操作的复杂度与树高线性相关,为 O(logq)O(\log q)O(logq);利用与替罪羊树类似的均摊分析,可以得到重构操作的均摊复杂度为 O(log2q)O\left(\log^2 q\right)O(log2q)。因此一次加入点的时间复杂度为 O(log2qlogC)O\left(\log^2q\log C\right)O(log2qlogC)。而查询第 kkk 大的操作需要进行 O(logC)O(\log C)O(logC) 次 k-d tree 上的范围查询,每次范围查询的时间复杂度为 O(q1/2)O\left(q^{1/2}\right)O(q1/2),则一次查询第 kkk 大的时间复杂度为 O(q1/2logC)O\left(q^{1/2}\log C\right)O(q1/2logC)。假设插入和查询操作个数同阶(事实如此),则总时间复杂度为 O(qlog2qlogC+q3/2logC)O\left(q\log^2 q\log C+q^{3/2}\log C\right)O(qlog2qlogC+q3/2logC)。这样分析得到的是复杂度的上界,实际运行时间基本不会达到这个级别。
代码
#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
const int MAXN = 100031, MAXV = 1000000002, MAXL = 31;
struct P {
int x[2];
P(int x0 = 0, int x1 = 0) : x{x0, x1} {}
void update(const P &u, int d) {
if ((u.x[0] > x[0]) == d) x[0] = u.x[0];
if ((u.x[1] > x[1]) == d) x[1] = u.x[1];
}
bool in(const P &u) const {
return x[0] <= u.x[0] && x[1] <= u.x[1];
}
};
namespace K {
struct N {
N *lc, *rc;
P x, l, r;
int s;
void update() {
s = 1;
if (lc) l.update(lc->l, 0), r.update(lc->r, 1), s += lc->s;
if (rc) l.update(rc->l, 0), r.update(rc->r, 1), s += rc->s;
}
} pl[MAXN * MAXL], *tp = pl, *rp[MAXN * MAXL], **rtp = rp;
struct C {
int d;
C(int _d = 0) : d(_d) {}
bool operator()(const N *a, const N *b) {
return a->x.x[d] < b->x.x[d];
}
};
void fltn(N *p) {
if (p) fltn(p->lc), fltn(p->rc), *(rtp++) = p;
}
void build(N *&p, int l, int r, int d) {
if (l == r) p = 0;
else {
int mid = (l + r) >> 1;
std::nth_element(rp + l, rp + mid, rp + r, C(d));
p = rp[mid];
p->l = p->r = p->x;
build(p->lc, l, mid, d ^ 1), build(p->rc, mid + 1, r, d ^ 1);
p->update();
}
}
void rbld(N *&p, int d) {
rtp = rp;
int n = p->s;
fltn(p), build(p, 0, n, d);
}
bool nrb = 0;
double ALPHA = 0.67, LA = -log(ALPHA);
void ins(N *&p, const P &x, int d, int dpt, int sz) {
if (!p) {
*(p = tp++) = {0, 0, x, x, x, 1};
nrb = dpt > log(sz + 2) / LA;
} else {
if (x.x[d] < p->x.x[d]) ins(p->lc, x, d ^ 1, dpt + 1, sz);
else ins(p->rc, x, d ^ 1, dpt + 1, sz);
p->s++;
if (nrb) {
double lim = ALPHA * p->s;
if ((p->lc && p->lc->s > lim) || (p->rc && p->rc->s > lim)) rbld(p, d), nrb = 0;
}
p->update();
}
}
void ins(N *&p, const P &x) {
ins(p, x, 0, 0, p ? p->s : 0);
}
int query(N *p, const P &l, const P &r) {
if (!p || !(l.in(p->r) && p->l.in(r))) return 0;
if (l.in(p->l) && p->r.in(r)) return p->s;
return (l.in(p->x) && p->x.in(r)) + query(p->lc, l, r) + query(p->rc, l, r);
}
}
namespace T {
struct N {
N *lc, *rc;
K::N *x;
} pl[MAXN * MAXL] = {{pl, pl, 0}}, *tp = pl, *nil = tp++, *rt = nil;
void ins(N *&p, int l, int r, const P &x, int v) {
if (p == nil) p = new (tp++) N(*nil);
K::ins(p->x, x);
if (l + 1 != r) {
int mid = (l + r) >> 1;
v < mid ? ins(p->lc, l, mid, x, v) : ins(p->rc, mid, r, x, v);
}
}
int query(N *p, int l, int r, const P &xl, const P &xr, int k) {
if (l + 1 == r) return l;
int mid = (l + r) >> 1, s = K::query(p->rc->x, xl, xr);
return k > s ? query(p->lc, l, mid, xl, xr, k - s) : query(p->rc, mid, r, xl, xr, k);
}
}
int main() {
int q = 0;
for (int t = scanf("%*d%d", &q), x0 = 0, y0 = 0, x1 = 0, y1 = 0, k = 0, lans = 0; q--; )
if (scanf("%d", &t), t == 1) scanf("%d%d%d", &x0, &y0, &k), T::ins(T::rt, 0, MAXV, P(x0 ^ lans, y0 ^ lans), k ^ lans);
else {
scanf("%d%d%d%d%d", &x0, &y0, &x1, &y1, &k);
if (lans = T::query(T::rt, 0, MAXV, P(x0 ^ lans, y0 ^ lans), P(x1 ^ lans, y1 ^ lans), k ^ lans)) printf("%d\n", lans);
else puts("NAIVE!ORZzyz.");
}
return 0;
}
您无敌了!
你咋不写博客了? %%%钊队