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

ydc的博客

 
 
 

日志

 
 

bzoj 2819 nim  

2013-06-06 17:18:59|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
就是查询区间路径异或值。
由于n达到了500000,虽然没试过但我相信link-cut-tree是不可能跑得过得
由于异或操作具有区间减法的性质,我们可以用DFS序加树状数组进行维护
对于一棵子树,他在DFS序一定是一个连续区间;于是我们就能用树状数组维护一个点到根的异或值了
然后每次修改就是把对应区间修改一下;每次查询的时候,我们用倍增法计算出其lca,然后用树状数组计算两个点到根的异或值再异或lca的石子个数,就得到了这条链的异或值了
然后DFS会爆栈
所以第一次写了人工栈
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 500010
#define maxm 1000010
#define lowbit(x) ((x)&(-x))
using namespace std;
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
int F[maxn][20],dep[maxn],SumXor[maxn];
int nStone,stone[maxn];
int pos[maxn],seq[maxn],match[maxn],tot;
int nEdge,to[maxn],next[maxn],start[maxn];
void make(int a,int b)
{
nEdge++,to[nEdge]=b,next[nEdge]=start[a],start[a]=nEdge;
}
void Insert(int p,int v)
{
for(int i=p;i<=nStone+1;i+=lowbit(i))
SumXor[i]^=v;
}
int Query(int p)
{
int ans=0;
for(int i=p;i;i-=lowbit(i))
ans^=SumXor[i];
return ans;
}
void Seq_DFS(int p)
{
static int edge[maxn],stack[maxn];
int top=0;
for(int i=1;i<=nStone;i++)
edge[i]=start[i];
stack[++top]=p,seq[++tot]=p,pos[p]=1;
while(1)
{
if(p==0)
break;
if(edge[p]==0)
{
match[p]=tot+1;
p=stack[--top];
edge[p]=next[edge[p]];
continue;
}
seq[++tot]=p=stack[++top]=to[edge[p]];
pos[p]=tot;
}
}
void read()
{
Read(nStone);
for(int i=1;i<=nStone;i++)
Read(stone[i]);
static int nG,toG[maxm],nextG[maxm],startG[maxn];
for(int i=2,a,b;i<=nStone;i++)
{
Read(a),Read(b);
nG++,toG[nG]=b,nextG[nG]=startG[a],startG[a]=nG;
nG++,toG[nG]=a,nextG[nG]=startG[b],startG[b]=nG;
}
static int queue[maxn];
static bool flag[maxn];
int front=0,rear=1;
queue[rear]=1,flag[1]=true,dep[1]=1;
while(front<rear)
{
int p=queue[++front];
for(int i=startG[p],q;i;i=nextG[i])
if(flag[q=toG[i]]==false)
{
F[q][0]=p,dep[q]=dep[p]+1;
flag[q]=true;
queue[++rear]=q;
make(p,q);
}
}
for(int i=1;i<=19;i++)
for(int j=1;j<=nStone;j++)
F[j][i]=F[F[j][i-1]][i-1];
Seq_DFS(1);
for(int i=1;i<=nStone;i++)
{
Insert(pos[i],stone[i]);
Insert(match[i],stone[i]);
}
}
int LCA(int a,int b)
{
if(dep[a]<dep[b])
swap(a,b);
for(int i=19;i>=0;i--)
{
if(dep[F[a][i]]>=dep[b])
a=F[a][i];
if(dep[a]==dep[b])
break;
}
if(a==b)
return a;
for(int i=19;i>=0;i--)
if(F[a][i]!=F[b][i])
a=F[a][i],b=F[b][i];
return F[a][0];
}
void Query()
{
int m;
char task[10];
Read(m);
for(int i=1,a,b;i<=m;i++)
{
scanf("%s",task);
Read(a),Read(b);
if(task[0]=='Q')
{
int lca=LCA(a,b);
printf("%s\n",Query(pos[a])^Query(pos[b])^stone[lca]?"Yes":"No");
}
else
{
Insert(pos[a],stone[a]);
Insert(match[a],stone[a]);
stone[a]=b;
Insert(pos[a],stone[a]);
Insert(match[a],stone[a]);
}
}
}
int main()
{
read();
Query();
return 0;
}


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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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