首页 > 代码库 > 【bzoj4605】崂山白花蛇草水 权值线段树套KD-tree
【bzoj4605】崂山白花蛇草水 权值线段树套KD-tree
题目描述
神犇Aleph在SDOI Round2前立了一个flag：如果进了省队，就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实力，他轻松地进了山东省省队，现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了999,999,999,999,999,999瓶崂山白花蛇草水，想要灌神犇Aleph。神犇Aleph求（跪着的）蒟蒻Bob不要灌他，由于神犇Aleph是神犇，蒟蒻Bob最终答应了他的请求，但蒟蒻Bob决定将计就计，也让神犇Aleph回答一些问题。具体说来，蒟蒻Bob会在一个宽敞的广场上放置一些崂山白花蛇草水（可视为二维平面上的一些整点），然后询问神犇Aleph在矩形区域(x1, y1), (x2, y2)(x1≤x2且y1≤y2，包括边界)中，崂山白花蛇草水瓶数第k多的是多少。为了避免麻烦，蒟蒻Bob不会在同一个位置放置两次或两次以上的崂山白花蛇草水，但蒟蒻Bob想为难一下神犇Aleph，希望他能在每次询问时立刻回答出答案。神犇Aleph不屑于做这种问题，所以把这个问题交给了你。
输入
输入的第一行为两个正整数N, Q，表示横纵坐标的范围和蒟蒻Bob的操作次数（包括放置次数和询问次数）。
接下来Q行，每行代表蒟蒻Bob的一个操作，操作格式如下：
首先第一个数字type，表示操作种类。type=1表示放置，type=2表示询问。
若type=1，接下来会有三个正整数x, y, v，表示在坐标整点(x, y)放置v瓶崂山白花蛇草水。(1≤x, y≤N, 1≤v≤10^9)
若type=2，接下来会有五个正整数x1, y1, x2, y2, k，表示询问矩形区域(x1, y1), (x2, y2)中，崂山白花蛇草水瓶数第k多的是多少。
(1≤x1≤x2≤N，1≤y1≤y2≤N，1≤k≤Q)
为了体现程序的在线性，你需要将每次读入的数据（除了type值）都异或lastans，其中lastans表示上次询问的答案。如果上次询问的答案为"NAIVE!ORZzyz."（见样例输出），则将lastans置为0。初始时的lastans为0。
初始时平面上不存在崂山白花蛇草水。
本题共有12组测试数据。对于所有的数据，N≤500,000。
Q的范围见下表：
测试点1-2 Q=1,000
测试点3-7 Q=50,000
测试点8-12 Q=100,000
输出
对于每个询问(type=2的操作)，回答崂山白花蛇草水瓶数第k多的是多少。若不存在第k多的瓶数，
请输出"NAIVE!ORZzyz."（输出不含双引号）。
样例输入
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 3000010using 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。