<div class="post_brief"><p>
有离线镜像还是能省不少流量。开心。不过流量还是用得飞快啊。</p>

 

这就是个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", &amp;n);
for (int i = 0; i &lt; n; ++ i)
	for (int j = 0; j &lt; n; ++ j) {
		scanf("%d", a[i] + j); 
		pret[i][j] = 0;
	}
scanf("%d", &amp;m);
rt = sgtBuild(0, m + 1);
for (int i = 1; i &lt;= m; ++ i) {
	int x, y;
	scanf("%d%d", &amp;x, &amp;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 &lt; n; ++ i)
	for (int j = 0; j &lt; 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 &lt;= m; ++ i)
	printf("%d %d\n", ansb[i], answ[i]);



}