题解：P4848 崂山白花蛇草水
zhang_kevin · · 题解
使用线段树套 K-D Tree 解决本题。
外层开一个值域线段树，树上每个节点
每次插入时，把“
查询时，先调用右孩子的 K-D Tree 判断点的个数，再决定往哪里递归即可。
由于强制在线难以离散化，故外层值域线段树需要动态开点。
最后可能需要卡常数和空间，一些技巧：
-
可以只维护右孩子的 K-D Tree，因为不查左孩子（可以有效优化空间，
49pts \to 84pts ）。 -
不用单独判无解，值域开到
0 即可。 -
把线段树值域上界增加一个随机数，扰动线段树结构，使 Hack 失效。
参考代码（依赖评测机波动与随机种子）：
#include<bits/stdc++.h>
// #define int long long
#define fo(i, l, r) for(decltype((l) + (r)) i = (l); i <= (r); ++i)
#define fd(i, l, r) for(decltype((l) + (r)) i = (l); i >= (r); --i)
#define fu(i, l, r) for(decltype((l) + (r)) i = (l); i < (r); ++i)
#define y1 zhang_kevin
#define pii pair<int, int>
#define fi first
#define se second
#define vec vector
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ll long long
#define ull unsigned long long
#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define puts wrs
using namespace std;
bool ST;
char ibuf[1 << 20], *p1 = ibuf, *p2 = ibuf, obuf[1 << 20], *p3 = obuf;
inline char gc(){
if(p1 == p2){
p1 = ibuf, p2 = ibuf + fread(ibuf, 1, 1 << 20, stdin);
if(p1 == p2) return EOF;
return *p1++;
}
return *p1++;
}
inline char pc(char ch){
if(p3 == obuf + (1 << 20)) flush();
*p3 = ch;
return *p3++;
}
template<typename type>
inline int rd(type &x){
x = 0; bool f = 0; char ch = gc();
while(!isdigit(ch)) f |= ch == '-', ch = gc();
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
return f ? x = -x : 0;
}
template<typename type, typename ...T>
inline void rd(type &x, T &...y){rd(x), rd(y...);}
class Flush{public: ~Flush(){flush();}}_;
template<typename type>
inline void wr(type x){
if(x < 0) pc('-'), x = -x;
if(x > 9) wr(x / 10);
pc(x % 10 + '0');
return;
}
inline void wrs(const string& s){for(auto ch : s) pc(ch);}
namespace Solution{
const int k = 2;
struct KDTree{
struct Node{
int l[k], r[k], d[k];
int ls, rs, sum;
}t[2000005]; int tot = 0;
inline int newnode(int x[]){
tot++;
fu(i, 0, k) t[tot].l[i] = t[tot].r[i] = t[tot].d[i] = x[i];
t[tot].ls = t[tot].rs = 0, t[tot].sum = 1;
return tot;
}
inline void push_up(int p){
fu(i, 0, k) t[p].l[i] = t[p].r[i] = t[p].d[i];
t[p].sum = 1;
if(t[p].ls){
fu(i, 0, k) t[p].l[i] = min(t[p].l[i], t[t[p].ls].l[i]);
fu(i, 0, k) t[p].r[i] = max(t[p].r[i], t[t[p].ls].r[i]);
t[p].sum += t[t[p].ls].sum;
}
if(t[p].rs){
fu(i, 0, k) t[p].l[i] = min(t[p].l[i], t[t[p].rs].l[i]);
fu(i, 0, k) t[p].r[i] = max(t[p].r[i], t[t[p].rs].r[i]);
t[p].sum += t[t[p].rs].sum;
}
return;
}
int axis;
inline int build(vec<int>& id, int l, int r, int dep){
if(l > r) return 0;
int mid = (l + r) >> 1; axis = dep % k;
auto cmp = [this](int x, int y){return t[x].d[axis] < t[y].d[axis];};
nth_element(id.begin() + l, id.begin() + mid, id.begin() + r + 1, cmp);
int p = id[mid];
t[p].ls = build(id, l, mid - 1, dep + 1);
t[p].rs = build(id, mid + 1, r, dep + 1);
push_up(p);
return p;
}
inline int judge(int p, int l[], int r[]){
if(!p) return 0;
fu(i, 0, k) if(t[p].r[i] < l[i] || t[p].l[i] > r[i]) return 0;
fu(i, 0, k) if(t[p].l[i] < l[i] || t[p].r[i] > r[i]) return 1;
return 2;
}
inline int query(int p, int l[], int r[]){
int state = judge(p, l, r);
if(!state) return 0;
if(state == 2) return t[p].sum;
bool in = true;
fu(i, 0, k){
if(t[p].d[i] < l[i] || t[p].d[i] > r[i]){
in = false;
break;
}
}
return query(t[p].ls, l, r) + query(t[p].rs, l, r) + in;
}
inline void push_out(int p, vec<int> &o){
if(!p) return;
push_out(t[p].ls, o), push_out(t[p].rs, o), o.pb(p);
return;
}
}kdt;
struct KDForest{
int rt[18]; bool used[18];
inline int query(int l[], int r[]){
int res = 0;
fu(i, 0, 18) res += kdt.query(rt[i], l, r);
return res;
}
inline void insert(int x[]){
vec<int> cur = {kdt.newnode(x)};
fu(i, 0, 18){
if(!used[i]){
used[i] = true;
rt[i] = kdt.build(cur, 0, cur.size() - 1, 0);
break;
}else{
kdt.push_out(rt[i], cur);
used[i] = false, rt[i] = 0;
}
}
return;
}
};
struct segt{int ls, rs; KDForest t;} t[6000005]; int rt, tot = 0;
inline void insert(int &p, int l, int r, int x[], int v, bool f){
if(v < l || v > r) return;
if(!p) p = ++tot;
int mid = (l + r) >> 1;
if(f) t[p].t.insert(x);
if(l == r) return;
insert(t[p].ls, l, mid, x, v, false), insert(t[p].rs, mid + 1, r, x, v, true);
return;
}
inline int query(int p, int l, int r, int ql[], int qr[], int v){
if(!p || l == r) return l;
int mid = (l + r) >> 1, right = t[t[p].rs].t.query(ql, qr);
if(right >= v) return query(t[p].rs, mid + 1, r, ql, qr, v);
return query(t[p].ls, l, mid, ql, qr, v - right);
}
int n, q, lst = 0;
inline void Solve(){
srand(time(0)); const int V = 1000000000 + rand() % 100 + 233;
cerr << V << '\n';
rd(n, q);
while(q--){
int op; rd(op);
if(op == 1){
int x[k], v; rd(x[0], x[1], v);
x[0] ^= lst, x[1] ^= lst, v ^= lst;
insert(rt, 0, V, x, v, false);
}else{
int l[k], r[k], v; rd(l[0], l[1], r[0], r[1], v);
l[0] ^= lst, l[1] ^= lst, r[0] ^= lst, r[1] ^= lst, v ^= lst;
lst = query(rt, 0, V, l, r, v);
if(!lst) wrs("NAIVE!ORZzyz."), pc('\n');
else wr(lst), pc('\n');
}
}
return;
}
}
bool ED;
signed main(){
clock_t START = clock();
// freopen("input.in", "r", stdin), freopen("output.out", "w", stdout);
Solution::Solve();
cerr << (double)(clock() - START) / CLOCKS_PER_SEC << " s" << '\n';
cerr << 1.0 * abs(&ED - &ST) / 1024 / 1024 << " MB" << '\n';
return 0;
}