BZOJ1453 [Wc]Dface双面棋盘

有离线镜像还是能省不少流量。开心。不过流量还是用得飞快啊。

这就是个cdq重构的题。学习了前几天xyz大爷讲的扔线段树的做法，省了不少代码。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

struct node {
	int v, c;
	node *next;
};
struct seg {
	int l, r;
	node *head;
	seg *ls, *rs;
};

const int maxa = 209;
const int maxn = 40009;
const int maxm = 10009;
const int maxnd = maxn * 23;
const int mov[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

#define upmax(_a_,_b_) { \
	if (_a_ < _b_) \
		_a_ = _b_; \
}
#define mkpos(_x_,_y_) (((_x_)<<16)|(_y_))
#define getx(_a_) ((_a_)>>16)
#define gety(_a_) ((_a_)&0x0000ffff)
#define nid(_x_,_y_) (((_x_)*n)+(_y_))

struct disjoint_set {
	int r[maxn], h[maxn];
	int vst[maxn], rst[maxn], ust[maxn], hst[maxn], tst;
	inline disjoint_set() {
		tst = 0;
	}
	void init(int n) {
		for (int i = 0; i < n; ++ i)
			r[i] = i, h[i] = 1;
	}
	int getRoot(int x) {
		for (; r[x] ^ x; x = r[x]);
		return x;
	}
	inline void merge(int u, int v) {
		u = getRoot(u), v = getRoot(v);
		if (h[u] < h[v])
			swap(u, v);
		vst[++ tst] = v;
		rst[tst] = r[v];
		r[v] = u;
		ust[tst] = u;
		hst[tst] = h[u];
		upmax(h[u], h[v] + 1);
	}
	void recover(int x) {
		while (tst > x) {
			r[vst[tst]] = rst[tst];
			h[vst[tst]] = hst[tst];
			-- tst;
		}
	}
};

node nlst[maxnd], *np(nlst);
seg slst[maxn * 3], *sp(slst), *rt;
int n, m, a[maxa][maxa], cc[maxa][maxa], pret[maxa][maxa], ansb[maxm], answ[maxm];

#define midp(_p_) ((_p_->l+_p_->r)>>1)

inline seg* sgtBuild(int l, int r) {
	seg* p(sp ++);
	p-> l = l;
	p-> r = r;
	p-> head = 0;
	if (l + 1 < r) {
		p-> ls = sgtBuild(l, midp(p));
		p-> rs = sgtBuild(midp(p), r);
	}
	return p;
}
inline void sgtIns(seg* p, int l, int r, int ps, int cl) {
	if (p-> l == l && p-> r == r) {
		np-> v = ps;
		np-> c = cl;
		np-> next = p-> head;
		p-> head = np ++;
	}
	else if (r <= midp(p))
		sgtIns(p-> ls, l, r, ps, cl);
	else if (l >= midp(p))
		sgtIns(p-> rs, l, r, ps, cl);
	else {
		sgtIns(p-> ls, l, midp(p), ps, cl);
		sgtIns(p-> rs, midp(p), r, ps, cl);
	}
}

disjoint_set r;

void sgtDfs(seg* p, int cb, int cw) {
	int rp(r. tst);
	for (node* it = p-> head; it; it = it-> next) {
		int x(getx(it-> v)), y(gety(it-> v)), c(it-> c), *v;
		if (c == 0)
			v = &cw;
		else
			v = &cb;
		++ *v;
		cc[x][y] = c;
		for (int mi = 0; mi < 4; ++ mi) {
			int x1(x + mov[mi][0]), y1(y + mov[mi][1]);
			if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= n)
				continue;
			if (cc[x1][y1] == c && r. getRoot(nid(x, y)) != r. getRoot(nid(x1, y1))) {
				-- *v;
				r. merge(nid(x, y), nid(x1, y1));
			}
		}
	}
	if (p-> l + 1 == p-> r) {
		ansb[p-> l] = cb;
		answ[p-> l] = cw;
	}
	else {
		sgtDfs(p-> ls, cb, cw);
		sgtDfs(p-> rs, cb, cw);
	}
	for (node* it = p-> head; it; it = it-> next) {
		int x(getx(it-> v)), y(gety(it-> v));
		cc[x][y] = -1;
	}
	r. recover(rp);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d", &n);
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < n; ++ j) {
			scanf("%d", a[i] + j); 
			pret[i][j] = 0;
		}
	scanf("%d", &m);
	rt = sgtBuild(0, m + 1);
	for (int i = 1; i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		-- x;
		-- y;
		sgtIns(rt, pret[x][y], i, mkpos(x, y), a[x][y]);
		a[x][y] ^= 1;
		pret[x][y] = i;
	}
	for (int i = 0; i < n; ++ i)
		for (int j = 0; j < n; ++ j)
			sgtIns(rt, pret[i][j], m + 1, mkpos(i, j), a[i][j]);
	memset(cc, 0, sizeof(cc));
	r. init(n * n);
	memset(cc, -1, sizeof(cc));
	sgtDfs(rt, 0, 0);
	for (int i = 1; i <= m; ++ i)
		printf("%d %d\n", ansb[i], answ[i]);
}