门户网站开发语言,WordPress支持api吗,免费产品网站建设,中小企业公司线段树专题-黑白棋盘
题目来源 BZOJ−1453BZOJ-1453BZOJ−1453
题意 QQQ次操作每次操作给出(x,y)(x,y)(x,y),将(x,y)(x,y)(x,y)个格子颜色取反每次操作后,输出棋盘上黑白联通块的个数n≤100,Q≤104n \le 100,Q \le 10^4n≤100,Q≤104
题解
显然不能直接套并查集,因为直接套…线段树专题-黑白棋盘
题目来源
BZOJ−1453BZOJ-1453BZOJ−1453
题意
QQQ次操作每次操作给出(x,y)(x,y)(x,y),将(x,y)(x,y)(x,y)个格子颜色取反每次操作后,输出棋盘上黑白联通块的个数n≤100,Q≤104n \le 100,Q \le 10^4n≤100,Q≤104
题解
显然不能直接套并查集,因为直接套并查集的时间复杂度为O(n2Q)108O(n^2Q) 10^8O(n2Q)108
考虑使用线段树维护并查集.
线段树维护的是[l,r][l,r][l,r]行中黑白联通块的数量,其中重点维护l,rl,rl,r两行的并查集.
遇到合并操作的时候,如把[l1,r1][l_1,r_1][l1,r1]与[l2,r2][l_2,r_2][l2,r2]做合并.
首先将各自的黑白联通块数量合并到[l1,r2][l_1,r_2][l1,r2]中去,然后再从中减去并查集合并时候造成的联通块减小的部分数.
首先构建一颗大小为4n4n4n的并查集,把l1l_1l1并查集放于第一层,r1r1r1并查集放于第二层,把l2l_2l2并查集放于第三层,r2r2r2并查集放于第四层.注意此时第一层和第二层有关系,第三层和第四层有关系.然后枚举i:[1,n]i : [1,n]i:[1,n],打通第二层和第三层之间的关系,并更新黑白联通块的个数.
因为中间的二三层在做完以上操作的时候已经没有用了,因此我们要把它们删掉,并且将规模4n4n4n的并查集缩小至2n2n2n.
我们需要玩一个小trictrictric,即把第一层的并查集的根节点全都换成第一层里的数,把第四层并查集里的根节点全都换成第二层里的数.这样的话并查集又可以缩小为2n2n2n了.
小tric的代码
rep(i,1,n) {tmp[findset(pa,pa[i])] i;tmp[findset(pa,pa[i3*n])] in;
}
rep(i,1,n) {ns[rt].pa[i] tmp[findset(pa,pa[i])];ns[rt].pa[in] tmp[findset(pa,pa[i3*n])];
}代码
#include cstdio
#include iostream#define rep(x,a,b) for(int x a;x b;x)
#define pr(x) std::cout #x : x std::endl
const int N 201;
int n,m;
int bit[N][N];
void initset(int pa[],int n) {rep(i,1,n) pa[i] i;}
int findset(int pa[],int x) {return x pa[x]?x:pa[x] findset(pa,pa[x]);}
int join(int pa[],int x,int y) {int px findset(pa,x),py findset(pa,y);if(px ! py) {pa[px] py;return true;}return false;
}
struct Node{int pa[2*N];int color[2];void init(int line) {color[0] color[1] 0;initset(pa,n);rep(i,1,n-1) if(bit[line][i] bit[line][i1])join(pa,i1,i);rep(i,1,n) pa[in] pa[i];rep(i,1,n)if(findset(pa,i) i) color[bit[line][i]] ;}
}ns[N2];
int pa[N2],tmp[N2];
void maintain(int rt,int l,int r){int mid (l r) / 2;int lc rt 1,rc rt 1 | 1;rep(i,1,2*n) {pa[i] ns[lc].pa[i];pa[i2*n] ns[rc].pa[i] 2*n;}ns[rt].color[0] ns[lc].color[0] ns[rc].color[0];ns[rt].color[1] ns[lc].color[1] ns[rc].color[1];rep(i,1,n) {if(bit[mid][i] bit[mid1][i]) {if(join(pa,i2*n,in)){ns[rt].color[bit[mid][i]] --;}}}rep(i,1,n) {tmp[findset(pa,pa[i])] i;tmp[findset(pa,pa[i3*n])] in;}rep(i,1,n) {ns[rt].pa[i] tmp[findset(pa,pa[i])];ns[rt].pa[in] tmp[findset(pa,pa[i3*n])];}
}
void build(int rt,int l,int r) {if(l r) {ns[rt].init(l);return ;}int mid (l r) / 2;build(rt1,l,mid);build(rt1|1,mid1,r);maintain(rt,l,r);
}
void change(int rt,int l,int r,int pos) {if(l r) ns[rt].init(l);else {int mid (l r) / 2;if(pos mid) change(rt1,l,mid,pos);else change(rt1|1,mid1,r,pos);maintain(rt,l,r);}
}
int main() {std::ios::sync_with_stdio(false);std::cin n;rep(i,1,n) rep(j,1,n) {std::cin bit[i][j];}build(1,1,n);//std::cout ns[1].color[0] ns[1].color[1] std::endl;std::cin m;while(m--) {int x,y;std::cin x y;bit[x][y] ^ 1;change(1,1,n,x);std::cout ns[1].color[1] ns[1].color[0] std::endl;}
}
