1453: [Wc]Dface双面棋盘

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 617  Solved: 317
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

 
 
 
用线段树+数组模拟并查集,维护每一列的连通性,然后暴力合并就行了,常数巨大
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 210
int father[N<<],tmp[N<<],n,m,a[N][N];
struct Node{
int l,r;
int le[N],ri[N];
int lb[N],rb[N];
int s0,s1;
}tree[N<<]; inline int find(int x){
if(father[x]!=x)father[x]=find(father[x]);
return father[x];
}
void update(int rt){
tree[rt].s0=tree[rt<<].s0+tree[rt<<|].s0;
tree[rt].s1=tree[rt<<].s1+tree[rt<<|].s1;
memcpy(tree[rt].lb,tree[rt<<].lb,sizeof tree[rt].lb);
memcpy(tree[rt].rb,tree[rt<<|].rb,sizeof tree[rt].rb);
for(int i=;i<=n<<;i++) father[i]=i;
for(int i=;i<=n;i++) tree[rt<<|].le[i]+=*n,tree[rt<<|].ri[i]+=*n;
for(int i=;i<=n;i++){
int x=tree[rt<<].ri[i],y=tree[rt<<|].le[i];
if(find(x)!=find(y)&&tree[rt<<].rb[i]==tree[rt<<|].lb[i]){
father[find(x)]=find(y);
if(tree[rt<<].rb[i]){
tree[rt].s1--;
}else{
tree[rt].s0--;
}
}
}
for(int i=;i<=n;i++) tree[rt].le[i]=find(tree[rt<<].le[i]),
tree[rt].ri[i]=find(tree[rt<<|].ri[i]);
for(int i=;i<=n;i++) tmp[i<<]=tree[rt].le[i],tmp[(i<<)-]=tree[rt].ri[i];
sort(tmp+,tmp++*n);
int mxdata=unique(tmp+,tmp++*n)-tmp-;
for(int i=;i<=n;i++) tree[rt].le[i]=lower_bound(tmp+,tmp++mxdata,
tree[rt].le[i])-tmp,tree[rt].ri[i]=lower_bound(tmp+,tmp++mxdata,tree[rt].ri[i])-tmp;
for(int i=;i<=n;i++) tree[rt<<|].le[i]-=*n,tree[rt<<|].ri[i]-=*n;
} void build(int l,int r,int rt){
tree[rt].l=l;tree[rt].r=r;
if(l==r){
int tot=;
for(int i=;i<=n;i++)
{
if(a[i][l]!=a[i-][l])
{
tot++;
if(a[i][l]) tree[rt].s1++;
else tree[rt].s0++;
}
tree[rt].le[i]=tree[rt].ri[i]=tot;
tree[rt].lb[i]=tree[rt].rb[i]=a[i][l];
}
return;
}
int mid=(l+r)>>;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
update(rt);
} void modify(int rt,int pos)
{
if(tree[rt].l==tree[rt].r)
{
int tot=;tree[rt].s1=;tree[rt].s0=;
for(int i=;i<=n;i++)
{
if(a[i][pos]!=a[i-][pos])
{
tot++;
if(a[i][pos]) tree[rt].s1++;
else tree[rt].s0++;
}
tree[rt].le[i]=tree[rt].ri[i]=tot;
tree[rt].lb[i]=tree[rt].rb[i]=a[i][pos];
}
return;
}
int mid=(tree[rt].l+tree[rt].r)>>;
if(pos<=mid) modify(rt<<,pos);
else modify(rt<<|,pos);
update(rt);
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++){
a[][i]=-;
for(int j=;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
build(,n,);
scanf("%d",&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
a[x][y]^=;
modify(,y);
printf("%d %d\n",tree[].s1,tree[].s0);
}
return ;
}

最新文章

  1. mysql基本操作
  2. Clock rate
  3. [字符哈希] POJ 3094 Quicksum
  4. java8中的map和reduce
  5. FPGA保留信号的语句
  6. QT 信号与槽连接
  7. PHP学习笔记——PHP脚本和JAVA连接mysql数据库
  8. 亲测linux上安装mysql
  9. [Angular 2] Mapping Streams to Values to Affect State
  10. Starship Troopers(HDU 1011 树形DP)
  11. Super Jumping! Jumping! Jumping! 基础DP
  12. Mac上配置不同版本的JDK
  13. Log4j 2X 日志文件路径问题
  14. Markdown 指南
  15. scikit-FEM-mesh
  16. InstallShield中打包ArcEnineRuntime
  17. 836. Rectangle Overlap 矩形重叠
  18. hdu 2049 不容易系列之考新郎 && 对错排的详解
  19. 第一部分 OpenStack及其构成简介
  20. BZOJ 2743: [HEOI2012]采花 离线树状数组

热门文章

  1. (转)rvm安装与常用命令
  2. poj--1064
  3. Jenkins自动化搭建测试环境(一)
  4. python redis中blpop和lpop的区别
  5. Linux Shell系列教程之(九)Shell判断 if else 用法
  6. Swift 3:新的访问控制fileprivate和open
  7. HDU2098 分拆素数和
  8. BZOJ3990 [SDOI2015]排序 【搜索】
  9. 洛谷 P1131 选择客栈
  10. polyfill for Function--源码