题目描述
输入
输出
样例输入
10 7
1 1 1 1
1 2 2 3
1 4 1 2
1 3 4 4
2 1 1 4 1 3
2 2 2 3 5 4
2 2 1 4 4 2
样例输出
NAIVE!ORZzyz.
NAIVE!ORZzyz.
3
题解
权值线段树套KD-tree
一开始想到了一个$O(n\sqrt n\log^2n)$的KD-tree套平衡树套二分的傻*做法本以为数据水能卡过去，结果自己做的随机极限数据跑了60s++。。
看来以后是再也不能过于相信数据结构了。
本题正解是权值线段树/替罪羊树套KD-tree，由于蒟蒻没有学替罪羊树就写了动态开点权值线段树。
对于外层权值线段树的每个节点，对应着一棵KD-tree，存储权值在外层节点范围内的所有点。
对于每次询问，如果判定有解，则寻找区间右半部分中点的个数，如果大于等于k则在右区间中找，否则在左区间中找，直至l=r得到答案。
嗯，说起来真是容易。然而这样交上去肯定是必T无疑。
究其原因就是在KD-tree上。（警察叔叔，就是他！）
一开始把“平衡”KD-tree的时间复杂度当成$O(\log n)$的了（这也是我一开始想出那个做法的原因），以为稳过，结果卡得很死。
由于KD-tree不能旋转什么的，所以自然不能保证平衡。
那么我们能做的只有对KD-tree进行重构，但是蒟蒻又不会比例重构（子树大小超过某比例时重构，替罪羊树的操作），所以只能固定点数重构。
然而重构又出了各种各样的问题 = =，改了以后交上去还是TLE。
实在没办法，要了份数据，发现第6、7个点卡不重构的KD-tree，第8、9、10个点数据范围非常大，这导致无论怎么改重构时间都无法通过。
最后只能针对数据来解决问题了（逃），m=50000时是前7个点，m=100000时是后3个点，分情况就好了，最后还是勉强跑过了。
说实话真正考试如果出这种题的话80分真的是满足了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3000010
using namespace std;
const int M = 1000000000;
int m , R , ls[N] , rs[N] , root[N] , ts[N] , tot , d , num , x1 , y1 , x2 , y2;
int sta[N] , top;
struct data
{
int p[2] , mx[2] , mn[2] , si , c[2];
bool operator<(const data a)const {return p[d] == a.p[d] ? p[d ^ 1] < a.p[d ^ 1] : p[d] < a.p[d];}
}a[N];
bool cmp(int x , int y)
{
return a[x].p[d] == a[y].p[d] ? a[x].p[d ^ 1] < a[y].p[d ^ 1] : a[x].p[d] < a[y].p[d];
}
void pushup(int k)
{
int l = a[k].c[0] , r = a[k].c[1];
a[k].mx[0] = max(a[k].p[0] , max(a[l].mx[0] , a[r].mx[0]));
a[k].mx[1] = max(a[k].p[1] , max(a[l].mx[1] , a[r].mx[1]));
a[k].mn[0] = min(a[k].p[0] , min(a[l].mn[0] , a[r].mn[0]));
a[k].mn[1] = min(a[k].p[1] , min(a[l].mn[1] , a[r].mn[1]));
a[k].si = a[l].si + a[r].si + 1;
}
void insert(int &k)
{
if(!k) k = ++num , a[k].p[0] = x1 , a[k].p[1] = y1;
else if((d == 0 && (x1 == a[k].p[0] ? y1 < a[k].p[1] : x1 < a[k].p[0])) || (d == 1 && (y1 == a[k].p[1] ? x1 < a[k].p[0] : y1 < a[k].p[1]))) d ^= 1 , insert(a[k].c[0]);
else insert(a[k].c[1]);
pushup(k);
}
int query(int k)
{
if(!k || x1 > a[k].mx[0] || y1 > a[k].mx[1] || x2 < a[k].mn[0] || y2 < a[k].mn[1]) return 0;
if(x1 <= a[k].mn[0] && y1 <= a[k].mn[1] && x2 >= a[k].mx[0] && y2 >= a[k].mx[1]) return a[k].si;
int ans = (a[k].p[0] >= x1 && a[k].p[1] >= y1 && a[k].p[0] <= x2 && a[k].p[1] <= y2);
ans += query(a[k].c[0]);
ans += query(a[k].c[1]);
return ans;
}
int solve(int k , int l , int r , int x)
{
if(l == r) return l;
int mid = (l + r) >> 1 , sum = query(root[rs[x]]);
if(sum >= k) return solve(k , mid + 1 , r , rs[x]);
else return solve(k - sum , l , mid , ls[x]);
}
int build(int l , int r , int now)
{
if(l > r) return 0;
int mid = (l + r) >> 1 , pos;
d = now , nth_element(sta + l , sta + mid , sta + r + 1 , cmp) , pos = sta[mid];
a[pos].c[0] = build(l , mid - 1 , now ^ 1);
a[pos].c[1] = build(mid + 1 , r , now ^ 1);
pushup(pos);
return pos;
}
void dfs(int k)
{
if(!k) return;
sta[++top] = k;
dfs(a[k].c[0]) , dfs(a[k].c[1]);
}
void rebuild(int &k)
{
top = 0 , dfs(k);
k = build(1 , top , 0);
}
void add(int p , int l , int r , int &x)
{
if(!x) x = ++tot;
d = 0 , insert(root[x]) , ts[x] ++ ;
if(m == 50000 && ts[x] >= 2000) rebuild(root[x]) , ts[x] = 0;
if(l == r) return;
int mid = (l + r) >> 1;
if(p <= mid) add(p , l , mid , ls[x]);
else add(p , mid + 1 , r , rs[x]);
}
int main()
{
a[0].mx[0] = a[0].mx[1] = -M , a[0].mn[0] = a[0].mn[1] = M;
int ans = 0 , opt , v , i;
scanf("%*d%d" , &m);
for(i = 1 ; i <= m ; i ++ )
{
scanf("%d" , &opt);
if(opt == 1)
{
scanf("%d%d%d" , &x1 , &y1 , &v);
x1 ^= ans , y1 ^= ans , v ^= ans;
add(v , 1 , M , R);
}
else
{
scanf("%d%d%d%d%d" , &x1 , &y1 , &x2 , &y2 , &v);
x1 ^= ans , y1 ^= ans , x2 ^= ans , y2 ^= ans , v ^= ans;
if(query(root[R]) < v) puts("NAIVE!ORZzyz.") , ans = 0;
else printf("%d\n" , ans = solve(v , 1 , M , R));
}
}
return 0;
}
【bzoj4605】崂山白花蛇草水 权值线段树套KD-tree
原文：http://www.cnblogs.com/GXZlegend/p/7134099.html