注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 1453 双面棋盘  

2014-01-16 08:51:34|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这题不会做……于是去看题解了

建线段树,每个线段树维护[l,r]行里的答案以及上边界和下边界的连通情况
用并查集进行区间合并
时间复杂度O(m*log n*n*反阿克曼(n))
真是暴力

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 210
#define WHITE 0
#define BLACK 1
using namespace std;
struct Node
{
int L[maxn],R[maxn],sizeW,sizeB,numL,numR;
}Tree[maxn<<2];
int n,nTree,map[maxn][maxn];
int father[maxn*2];
int Find(int p)
{
if(father[p]!=p)
father[p]=Find(father[p]);
return father[p];
}
Node operator + (Node a,Node b)
{
static Node c;
static int cnt[maxn*4];
int max1=0;
for(int i=1;i<=n;++i)
max1=max(max1,a.L[i]),max1=max(max1,a.R[i]);
for(int i=1;i<=n;++i)
b.L[i]+=max1,b.R[i]+=max1;
for(int i=1;i<=2*n;++i)
cnt[i]=0,father[i]=i;
c.numL=a.numL,c.numR=b.numR,c.sizeW=a.sizeW+b.sizeW,c.sizeB=a.sizeB+b.sizeB;
for(int i=1;i<=n;++i)
c.L[i]=a.L[i],c.R[i]=b.R[i];
for(int i=1;i<=n;++i)
if(map[a.numR][i]==map[b.numL][i])
{
int px=Find(a.R[i]),py=Find(b.L[i]);
if(px!=py)
{
father[px]=py;
if(map[a.numR][i]==WHITE)
--c.sizeW;
else
--c.sizeB;
}
}
for(int i=1;i<=n;++i)
{
c.L[i]=Find(c.L[i]),c.R[i]=Find(c.R[i]);
if(father[c.L[i]]==c.L[i])
cnt[c.L[i]]=1;
if(father[c.R[i]]==c.R[i])
cnt[c.R[i]]=1;
}
for(int i=2;i<=2*n;++i)
cnt[i]+=cnt[i-1];
for(int i=1;i<=n;++i)
c.L[i]=cnt[father[c.L[i]]],c.R[i]=cnt[father[c.R[i]]];
return c;
}
void Modify(int p,int w)
{
map[p][w]^=1,p+=nTree;
int *a=Tree[p].L,*b=Tree[p].R;
int tot=0;
Tree[p].sizeW=Tree[p].sizeB=0;
for(int i=1;i<=n;++i)
{
a[i]=b[i]=tot;
if(i==1||map[p-nTree][i]!=map[p-nTree][i-1])
{
a[i]=b[i]=++tot;
if(map[p-nTree][i]==WHITE)
++Tree[p].sizeW;
else
++Tree[p].sizeB;
}
}
for(p>>=1;p;p>>=1)
Tree[p]=Tree[p<<1]+Tree[p<<1|1];
}
void Query(int l,int r)
{
static Node ansl,ansr;
bool markl=false,markr=false;
for(l=l+nTree-1,r=r+nTree+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)
{
if(markl==false)
ansl=Tree[l^1],markl=true;
else
ansl=ansl+Tree[l^1];
}
if(r&1)
{
if(markr==false)
ansr=Tree[r^1],markr=true;
else
ansr=Tree[r^1]+ansr;
}
}
if(markl==false)
printf("%d %d\n",ansr.sizeB,ansr.sizeW);
else if(markr==false)
printf("%d %d\n",ansl.sizeB,ansl.sizeW);
else
{
ansl=ansl+ansr;
printf("%d %d\n",ansl.sizeB,ansl.sizeW);
}
}
void read()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&map[i][j]);
for(nTree=1;nTree-2<n;nTree<<=1);
for(int i=nTree+1;i<=nTree+n;++i)
{
int *a=Tree[i].L,*b=Tree[i].R;
a[1]=b[1]=1;
Tree[i].numL=Tree[i].numR=i-nTree;
int tot=0;
for(int j=1;j<=n;++j)
{
a[j]=b[j]=tot;
if(j==1||map[i-nTree][j]!=map[i-nTree][j-1])
{
a[j]=b[j]=++tot;
if(map[i-nTree][j]==WHITE)
++Tree[i].sizeW;
else
++Tree[i].sizeB;
}
}
}
for(int i=nTree;i>=1;--i)
Tree[i]=Tree[i<<1]+Tree[i<<1|1];
}
void Query()
{
int m;
scanf("%d",&m);
for(int i=1,b,w;i<=m;++i)
{
scanf("%d %d",&b,&w);
Modify(b,w);
Query(1,n);
}
}
int main()
{
read();
Query();
return 0;
}

  评论这张
 
阅读(487)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017