[icpcarchive 6045 – Alien Abduction] Scapegoat Tree + KD Tree

今年雅加达的H题。OJ上一直没人过，然后自己写了一下，线段树套set TLE了几回，然后想起之前一直没敢写的Scapegoat Tree + KD Tree，试了一下居然AC了。
^_^哈哈，不得不说，这种拿题库FirstBlood的感觉真是爽。
传送门
【题意】

给定n(n<=50000)个在二维平面上的整点，坐标保证0<=x<=w, 0<=y<=h。再给定q(q<=50000)个操作，每个操作为给定一个点$$(x_i, y_i)$$，将离$$(x_i, y_i)$$曼哈顿距离小于等于$$E_i$$的点的坐标都作一个奇葩的变换。 $$X_i' = ((X_i * a) + (Y_i * b) + (i * c)) mod W$$ $$Y_i' = ((X_i * d) + (Y_i * e) + (i * f)) mod H$$ 然后在q次操作以后，把n个点的坐标输出来。题目保证，总共的变换次数不超过50000次。

【算法】
因为总共变换的次数不超过50000次，所以问题就在于如何快速地选中离$$(x_i, y_i)$$曼哈顿距离小于等于$$E_i$$的点。
显然满足条件的区域是一个旋转了45°的正方形，所以我们只要把坐标旋转45°就好了。也就是这样子：$$x’=x+y, y’=x-y+h$$。
好了，这样子问题就转化成如何快速选中一个所有边都平行于坐标轴的矩形内部点的问题。
显然这题直接用线段树套个set可以做到$$O(\log^2 n)$$ per operation. 但是无情地TLE……
尝试使用KD Tree解决。
显然把点都插入KDTree，然后询问就$$O(\sqrt n)$$的了。
但是有一个问题，选中这些点以后，要将其从KDTree中删除，将坐标变换以后再插入。而KDTree是一个类似二叉搜索树的数据结构，但坑爹的是不能旋转，这样若干次操作以后，KDTree就会退化。
打着想水过的念头写了一下，果断TLE。
一个可行的解决方案是操作了$$\sqrt n$$个结点以后，就rebuild整棵树。但这样整体复杂度就是$$O(n\sqrt n)$$的。
之前在ACM_DIY群问了一下这个问题，数据结构帝CLJ说Scapegoat_tree可以不旋转只rebuild就达到均摊$$\log n$$的复杂度。去膜拜过wiki以后，发现确实可以做到。
于是写了一下，居然就过了。
所谓Scapegoat_tree，就是如果左右子树中的某个size超过了$$\alpha$$*this->size，那么就rebuild这棵子树。虽然看起来很傻X，但是确实可以证明复杂度是lg级别的。当然$$0.5 < \alpha < 1$$。而所谓KDTree就是在第i层的子树都取其关于第i % K维的中位数的那个结点作为根，然后左右子树递归下去。不明白的建议看看英文wiki。【时空分析】最坏的计算量是$$50000 * \sqrt{50000}$$级别的。空间复杂度是O(n)的。【其它】截个图留念一下，这种现在只有我过掉这题的感觉真是好爽 :Delighted:

【代码】

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
template  void checkmin(T &t,T x){if (x < t) t = x;}
template  void checkmax(T &t,T x){if (x > t) t = x;}
template  void _checkmin(T &t, T x){if (t == -1) t = x; if (x < t) t = x;}
template  void _checkmax(T &t, T x){if (t == -1) t = x; if (x > t) t = x;}
typedef pair  PII;
typedef pair  PDD;
typedef long long lld;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
#define DEBUG(a) cout << #a" = " << (a) << endl;
#define DEBUGARR(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
const int N = 105555;
const int INF = 1000000000;
const double mul = 0.7;
int Tc;
int n, q, w, h;

struct point {
	int x, y, id, rx, ry;
	point() {}
	void trans() {
		rx = x + y;
		ry = x - y + h;
	}
}p[N], tp[N];

int pt, ptr_t;
struct Node {
	int size;
	bool exist, div;
	point mid;
	Node *lc, *rc;
	Node() {size = exist = 0;}

	bool judge() {
		return !size || lc->size > mul * size || rc->size > mul * size;
	}
}pool[N * 5], *root, *null = &pool[0], *ptr[N];

inline bool cmpx(const point &a, const point &b)  { return a.rx < b.rx || (a.rx == b.rx && a.id < b.id); }
inline bool cmpy(const point &a, const point &b)  { return a.ry < b.ry || (a.ry == b.ry && a.id < b.id); }
inline bool cmp(const point &a, const point &b, const bool &div) { return div ? cmpy(a, b) : cmpx(a, b); }

Node *build(point *a, int l, int r, bool div, bool type = 1) {
	if (l > r) return null;
	int mid = (l + r) / 2;
	Node *p = type ? &pool[pt++] : ptr[--ptr_t];
	nth_element(a + l, a + mid,  a + r + 1, div ? cmpy : cmpx);
	p->div = div;
	p->mid = a[mid];
	p->exist = 1;
	p->lc = build(a, l, mid - 1, !div, type);
	p->rc = build(a, mid + 1, r, !div, type);
	p->size = p->lc->size + p->rc->size + 1;
	return p;
}

void dfs(Node *p) {
	if (p == null) return;
	if (p->exist) {
		tp[ptr_t] = p->mid;
		ptr[ptr_t++] = p;
	}
	dfs(p->lc);
	dfs(p->rc);
}

void rebuild(Node *&p) {
	ptr_t = 0;
	dfs(p);
	p = build(tp, 0, ptr_t - 1, p->div, 0);
}


void insert(Node *&p, point a, bool div, bool re = 0) {
	if (p == null) {
		p = &pool[pt++];
		p->div = div;
		p->exist = 1;
		p->size = 1;
		p->mid = a;
		p->lc = p->rc = null;
	} else {
		p->size++;
		bool tag = p->judge();
		if (cmp(a, p->mid, div)) {
			insert(p->lc, a, !div, re | tag);
		} else {
			insert(p->rc, a, !div, re | tag);
		}
		if (!re && tag) rebuild(p);
	}
}

vector  vec;

void getvec(Node *&p, int lx, int ly, int rx, int ry, bool re = 0) {
	if (p->size == 0) return;
	if (p->exist && lx <= p->mid.rx && p->mid.rx <= rx && ly <= p->mid.ry && p->mid.ry <= ry) {
		vec.push_back(p->mid.id);
		p->exist = 0;
		p->size--;
	}
	bool tag = p->judge();
	if (p->div ? ly <= p->mid.ry : lx <= p->mid.rx) getvec(p->lc, lx, ly, rx, ry, re | tag);
	if (p->div ? ry >= p->mid.ry : rx >= p->mid.rx) getvec(p->rc, lx, ly, rx, ry, re | tag);
	p->size = p->lc->size + p->rc->size + p->exist;
	if (!re && tag) rebuild(p);
}

int main() {
	scanf("%d", &Tc);
	for (int ri = 1; ri <= Tc; ri++) {
		pt = 1;
		scanf("%d%d%d%d", &n, &q, &w, &h);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &p[i].x, &p[i].y);
			p[i].id = i;
			p[i].trans();
			tp[i] = p[i];
		}
		root = build(tp, 1, n, 0);
		for (int i = 0; i < q; i++) {
			int x, y, E, a, b, c, d, e, f;
			scanf("%d%d%d%d%d%d%d%d%d", &x, &y, &E, &a, &b, &c, &d, &e, &f);
			int lx, ly, rx, ry;
			lx = x + y - E;
			ly = x - y - E + h;
			rx = x + y + E;
			ry = x - y + E + h;
			checkmax(lx, 0);
			checkmax(ly, 0);
			checkmin(rx, w + h);
			checkmin(ry, w + h);
			vec.clear();
			getvec(root, lx, ly, rx, ry);
			foreach (it, vec) {
				lld ix = p[*it].x;
				lld iy = p[*it].y;
				int tx = ((ix * a) + (iy * b) + ((lld)(*it) * c)) % w;
				int ty = ((ix * d) + (iy * e) + ((lld)(*it) * f)) % h;
				p[*it].x = tx;
				p[*it].y = ty;
				p[*it].trans();
				insert(root, p[*it], 0);
			}
		}
		printf("Case #%d:\n", ri);
		for (int i = 1; i <= n; i++) {
			printf("%d %d\n", p[i].x, p[i].y);
		}
	}
}

“[icpcarchive 6045 – Alien Abduction] Scapegoat Tree + KD Tree”上的2条回复

parlin说：

6 1 月, 2013 3:03 上午

[comment]显然把点都插入KDTree，然后询问就O(log_n)的了。[/comment]

我咋记得是O(sqrt_n)呢？
1. edward_mj说：
  
  6 1 月, 2013 11:54 上午
  
  确实$$\sqrt n$$的……才发现我复杂度证错了。
  KDTree比线段树套平衡树快好像是因为$$\log^2 n$$和$$\sqrt n$$差不多大的关系。
  我写了好多题KDTree都比树套树之类的快，大概就是因为常数小一点的原因吧。

评论已关闭。