与 jlf 学长一起出的水题，强制在线的动态三维偏序。

题目大意

维护一个二维点集，每一个点有权值，支持两种操作：

• 加入一个坐标为 $(x,y)$ 并且权值为 $v$ 的点；
• 查询在所有满足 x0≤x≤x1x_0 \le x \le x_1x​0​​≤x≤x​1​​ 且 y0≤y≤y1y_0\le y\le y_1y​0​​≤y≤y​1​​ 的点中，第 $k$ 大的点权是多少。

操作总数为 $q$，强制在线。

1≤x,y≤1051\le x,y\le 10^51≤x,y≤10​5​​，1≤v≤1091\le v\le10^91≤v≤10​9​​，1≤q≤1051\le q\le10^51≤q≤10​5​​。

题目链接

BZOJ 4605

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 不支持旋转操作，需要使用类似替罪羊树的平衡方法，利用重构子树来保持树的平衡。（如果不重构是会被卡的哟）

假设点权 $v$ 的最大值为 $C$，则每个加入点的操作需要进行 $O(\log C)$ 次在 k-d tree 上的插入操作。k-d tree 上插入操作的复杂度与树高线性相关，为 $O(\log q)$；利用与替罪羊树类似的均摊分析，可以得到重构操作的均摊复杂度为 O(log2q)O\left(\log^2 q\right)O(log​2​​q)。因此一次加入点的时间复杂度为 O(log2qlogC)O\left(\log^2q\log C\right)O(log​2​​qlogC)。而查询第 $k$ 大的操作需要进行 $O(\log C)$ 次 k-d tree 上的范围查询，每次范围查询的时间复杂度为 O(q1/2)O\left(q^{1/2}\right)O(q​1/2​​)，则一次查询第 $k$ 大的时间复杂度为 O(q1/2logC)O\left(q^{1/2}\log C\right)O(q​1/2​​logC)。假设插入和查询操作个数同阶（事实如此），则总时间复杂度为 O(qlog2qlogC+q3/2logC)O\left(q\log^2 q\log C+q^{3/2}\log C\right)O(qlog​2​​qlogC+q​3/2​​logC)。这样分析得到的是复杂度的上界，实际运行时间基本不会达到这个级别。

代码

#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;
}