UAVLive6045 题意： 给了二维平面上的N个整点（\(N \leq 50000\)）。每次操作给了点\((x_i,y_i)\),需要曼哈顿距离小于\(E\)的点进行一个变换。 输出最后的点的坐标，保证变换次数不超过50000. 这题做的方法比较多。 KD树的做法就是先进行坐标选择，转化成找一个矩形内的点。 但是这样的KD树需要进行插入和删除，这样普通的KD树将不能保持平衡。 动态的KD树其实就是KD树结合了替罪羊树的思想。 当不平衡的时候，找替罪羊，然后整颗树进行重构。
/* ***
Author :kuangbin
Created Time :2014/9/30 23:07:14
File Name :E:\2014ACM\专题学习\KD树\UVALive6045.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MAXN = 100010;
const double alpha = 0.75;
struct Point{
int x,y,id;
};
struct Node{
Point e;
int size,nodeCount;
Node *lc,*rc;
bool div;
bool exist;
bool isBad(){
return lc->nodeCount > alpha*nodeCount+5 || rc->nodeCount > alpha*nodeCount+5;
}
inline void push_up(){
size = exist + lc->size + rc->size;
nodeCount = 1+lc->nodeCount+rc->nodeCount;
}
};
Node pool[MAXN],*tail,*root,null;
Node bc[MAXN];
int bc_top;
void init(){
tail = pool;
null = tail++;
null->lc = null->rc = null;
null->size = null->nodeCount = 0;
root = null;
bc_top = 0;
}
Node newNode(Point e){
Node p;
if(bc_top)p = bc[–bc_top];
else p = tail++;
p->e = e;
p->lc = p->rc = null;
p->size = p->nodeCount = 1;
p->exist = true;
return p;
}
inline bool cmpX(const Point &a,const Point &b){
return a.x < b.x || (a.x == b.x && a.y < b.y) || (a.x == b.x && a.y == b.y && a.id < b.id);
}
inline bool cmpY(const Point &a,const Point &b){
return a.y < b.y || (a.y == b.y && a.x < b.x) || (a.y == b.y && a.x == b.x && a.id < b.id);
}
inline bool cmp(const Point &a,const Point &b,bool div){
return div?cmpY(a,b):cmpX(a,b);
}
//注意a需要备份，否则就乱序
Node *build(Point *a,int l,int r,bool div){
if(l >= r)return null;
int mid = (l+r)/2;
nth_element(a+l,a+mid,a+r,div?cmpY:cmpX);
Node p = newNode(a[mid]);
p->div = div;
p->lc = build(a,l,mid,!div);
p->rc = build(a,mid+1,r,!div);
p->push_up();
return p;
}
void Travel(Node p,vector
if(p == null)return;
Travel(p->lc,v);
if(p->exist)v.push_back(p->e);
bc[bc_top++] = p;
Travel(p->rc,v);
}
Node divide(vector
if(l >= r)return null;
int mid = (l+r)/2;
nth_element(v.begin()+l,v.begin()+mid,v.begin()+r,div?cmpY:cmpX);
Node
p->div = div;
p->lc = divide(v,l,mid,!div);
p->rc = divide(v,mid+1,r,!div);
p->push_up();
return p;
}
inline void rebuild(Node &p){
vector
Travel(p,v);
p = divide(v,0,v.size(),p->div);
}
Node \
if(p == null){
p = newNode(a);
p->div = div;
return &null;
}
else {
p->nodeCount++;
p->size++;
Node res;
if(cmp(a,p->e,div))
res = insert(p->lc,a,!div);
else res = insert(p->rc,a,!div);
if(p->isBad())res = &p;
return res;
}
}
void insert(Point e){
Node p = insert(root,e,0);
if(*p != null)rebuild(*p);
}
vector
void getvec(Node p,int minx,int maxx,int miny,int maxy){
if(p->size == 0)return;
if(p->exist && minx <= p->e.x && p->e.x <= maxx && miny <= p->e.y && p->e.y <= maxy){
vec.push_back(p->e.id);
p->exist = 0;
p->size–;
}
if(p->div? miny <= p->e.y : minx <= p->e.x)getvec(p->lc,minx,maxx,miny,maxy);
if(p->div? maxy >= p->e.y : maxx >= p->e.x)getvec(p->rc,minx,maxx,miny,maxy);
p->push_up();
}
Point p[MAXN],p2[MAXN];
Point p3[MAXN];
int main()
{
int T;
scanf(“%d”,&T);
int iCase = 0;
int N,Q,W,H;
while(T–){
iCase++;
scanf(“%d%d%d%d”,&N,&Q,&W,&H);
init();
for(int i = 0;i < N;i++){
scanf(“%d%d”,&p[i].x,&p[i].y);
p[i].id = p2[i].id = i;
p2[i].x = p[i].x+p[i].y;
p2[i].y = p[i].x-p[i].y;
p3[i] = p2[i];
}
root = build(p3,0,N,0);
int X,Y,E,a,b,c,d,e,f;
while(Q–){
scanf(“%d%d%d%d%d%d%d%d%d”,&X,&Y,&E,&a,&b,&c,&d,&e,&f);
vec.clear();
int minx = X+Y-E;
int maxx = X+Y+E;
int miny = X-Y-E;
int maxy = X-Y+E;
getvec(root,minx,maxx,miny,maxy);
int sz = vec.size();
for(int i = 0;i < sz;i++){
int id = vec[i];
long long tx = p[id].x;
long long ty = p[id].y;
p[id].x = (tx\a+ty*b+(long long)(id+1)c)%W;
p[id].y = (tx\d+ty*e+(long long)(id+1)*f)%H;
p2[id].x = p[id].x+p[id].y;
p2[id].y = p[id].x-p[id].y;
insert(p2[id]);
}
}
printf(“Case #%d:\n”,iCase);
for(int i = 0;i < N;i++)
printf(“%d %d\n”,p[i].x,p[i].y);
}
return 0;
}
