首页 > 代码库 > 【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 并查集+Treap/STL-set
【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 并查集+Treap/STL-set
题目描述
了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：
1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C.
2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群．
给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛
输入
第1行输入N和C，之后N行每行输入一只奶牛的坐标．
输出
仅一行，先输出牛群数，再输出最大牛群里的牛数，用空格隔开．
样例输入
4 2
1 1
3 3
2 2
10 10
样例输出
2 3
题解
为了练习Treap找到的这道略神的题
首先直接处理曼哈顿距离不是特别容易，我们可以把所有的点绕着原点逆时针旋转45°，这样原来的点$(x,y)$就变为了$(\frac{x-y}{\sqrt 2},\frac{x+y}{\sqrt 2})$，查询的区域变为了矩形范围，切比雪夫距离（横纵坐标差的绝对值最大值）不超过$\frac c{\sqrt 2}$。
然后约掉$\frac 1{\sqrt 2}$，就变为普通的矩形区域查询问题。
先将所有变换后的点按照横坐标排序，然后从左往右扫，将左面横坐标不满足条件的点删除。然后考虑连边：我们没有必要将所有在范围之内的点与当前点连边，只需要将当前点与第一个纵坐标比它大的点、第一个纵坐标比它小的点，如果满足条件就连边。
证明：使用数学归纳法
两个点之间使用这种方法是一定能够连上的。
如果k个点连上了，且纵坐标都比当前点大，并且横坐标满足条件，如果这种方法是不成立的，那么不妨设y1、y2，其中y1为纵坐标最接近当前点，y2为要连的点，我们要证的就是“当前点与y2有边，与y1没有边”是假命题。证明显然~
纵坐标比当前点小的时候同理。
于是k+1个点也能连上。命题得证。
回到题中，删点加点、查询前驱后继可以使用平衡树，维护连通性可以使用并查集。最后扫一遍每个点即可得到答案。
时间复杂度$O(n\log n)$。
事实上，STL的set比Treap还快~
Treap：
#include <cstdio>#include <cstdlib>#include <algorithm>#define N 100010using namespace std;struct data{ int x , y;}a[N];typedef pair<int , int> pr;int l[N] , r[N] , rnd[N] , tot , root , f[N] , tmp , num[N];pr w[N];bool cmp(data a , data b){ return a.x < b.x;}void zig(int &k){ int t = l[k]; l[k] = r[t] , r[t] = k , k = t;}void zag(int &k){ int t = r[k]; r[k] = l[t] , l[t] = k , k = t;}void insert(int &k , pr x){ if(!k) k = ++tot , w[k] = x , rnd[k] = rand(); else if(x < w[k]) { insert(l[k] , x); if(rnd[l[k]] < rnd[k]) zig(k); } else { insert(r[k] , x); if(rnd[r[k]] < rnd[k]) zag(k); }}void del(int &k , pr x){ if(x == w[k]) { if(!l[k] || !r[k]) k = l[k] + r[k]; else if(rnd[l[k]] < rnd[k]) zig(k) , del(r[k] , x); else zag(k) , del(l[k] , x); } else if(x < w[k]) del(l[k] , x); else del(r[k] , x);}void pre(int k , pr x){ if(!k) return; else if(x < w[k]) pre(l[k] , x); else tmp = w[k].second , pre(r[k] , x);}void sub(int k , pr x){ if(!k) return; else if(x < w[k]) tmp = w[k].second , sub(l[k] , x); else sub(r[k] , x);}int find(int x){ return x == f[x] ? x : f[x] = find(f[x]);}int main(){ int n , c , i , u , v , p = 1 , ans = 0 , mx = 0; scanf("%d%d" , &n , &c); for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &u , &v) , a[i].x = u - v , a[i].y = u + v , f[i] = i; sort(a + 1 , a + n + 1 , cmp); for(i = 1 ; i <= n ; i ++ ) { while(p < i && a[i].x - a[p].x > c) del(root , pr(a[p].y , p)) , p ++ ; tmp = 0 , pre(root , pr(a[i].y , i)); if(tmp && a[i].y - a[tmp].y <= c) f[find(i)] = find(tmp); tmp = 0 , sub(root , pr(a[i].y , i)); if(tmp && a[tmp].y - a[i].y <= c) f[find(i)] = find(tmp); insert(root , pr(a[i].y , i)); } for(i = 1 ; i <= n ; i ++ ) num[find(i)] ++ ; for(i = 1 ; i <= n ; i ++ ) if(num[i]) ans ++ , mx = max(mx , num[i]); printf("%d %d\n" , ans , mx); return 0;}STL-set：
#include <cstdio>#include <algorithm>#include <set>#define N 100010using namespace std;struct data{ int x , y;}a[N];typedef pair<int , int> pr;set<pr> s;set<pr>::iterator it;int f[N] , num[N];bool cmp(data a , data b){ return a.x < b.x;}int find(int x){ return x == f[x] ? x : f[x] = find(f[x]);}int main(){ int n , c , i , u , v , p = 1 , ans = 0 , mx = 0; scanf("%d%d" , &n , &c); for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &u , &v) , a[i].x = u - v , a[i].y = u + v , f[i] = i; sort(a + 1 , a + n + 1 , cmp); for(i = 1 ; i <= n ; i ++ ) { while(p < i && a[i].x - a[p].x > c) s.erase(pr(a[p].y , p)) , p ++ ; it = s.upper_bound(pr(a[i].y , i)); if(it != s.end() && it->first - a[i].y <= c) f[find(i)] = find(it->second); if(it != s.begin() && a[i].y - (--it)->first <= c) f[find(i)] = find(it->second); s.insert(pr(a[i].y , i)); } for(i = 1 ; i <= n ; i ++ ) num[find(i)] ++ ; for(i = 1 ; i <= n ; i ++ ) if(num[i]) ans ++ , mx = max(mx , num[i]); printf("%d %d\n" , ans , mx); return 0;}
【bzoj1604】[Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 并查集+Treap/STL-set
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。