【BZOJ2908】又是nand

escription

首先知道A nand B=not(A and B) （运算操作限制了数位位数为K）比如2 nand 3，K=3，则2 nand 3=not (2 and 3)=not 2=5。

给出一棵树，树上每个点都有点权，定义树上从a到b的费用为0与路径上的点的权值顺次nand的结果，例如：从2号点到5号点顺次经过2->3->5，权值分别为5、7、2，K=3，那么最终结果为0 nand 5 nand 7 nand 2=7 nand 7 nand 2=0 nand 2=7，现在这棵树需要支持以下操作。

① Replace a b:将点a（1≤a≤N）的权值改为b。

② Query a b:输出点a到点b的费用。

请众神给出一个程序支持这些操作。

Input

第一行N，M，K，树的节点数量、总操作个数和运算位数。

接下来一行N个数字，依次表示节点i的权值。

接下来N-1行，每行两个数字a,b（1≤a,b≤N）表示a,b间有一条树边。

接下来M行，每行一个操作，为以上2类操作之一。

N、M≤100000，K≤32

Output

对于操作②每个输出一行，如题目所述。

Sample Input

3 3 3
2 7 3
1 2
2 3
Query 2 3
Replace 1 3
Query 1 1

Sample Output

4
7

题解：网上都说要拆位，那么我也拆位吧~（不拆位好像也能做？）

首先，nand满足交换律但不满足结合律。

我们先树剖，然后对于每一位，都用线段树维护tl[d][x]，代表如果该位是d，从左边来经过这个区间后会变成的数，tr[d][x]代表如果该位是d，从右往左经过这个区间后会变成的数。然后就是区间合并的事了~

对于询问a,b，我们先求出从a向上走到lca的变化，再求出从lca向下走到b的变化即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#define lson x<<1

#define rson x<<1|1

using namespace std;

int n,m,k,cnt;

char str[10];

const int maxn=100010;

int to[maxn<<1],next[maxn<<1],head[maxn],fa[maxn],dep[maxn],siz[maxn],top[maxn],son[maxn],p[maxn],q[maxn],st[maxn];

unsigned v[maxn];

struct seg

{

	bool tl[2][maxn<<2],tr[2][maxn<<2];

	void pushup(int x)

	{

		tl[0][x]=tl[tl[0][lson]][rson],tl[1][x]=tl[tl[1][lson]][rson];

		tr[0][x]=tr[tr[0][rson]][lson],tr[1][x]=tr[tr[1][rson]][lson];

	}

	void build(int l,int r,int x,int a)

	{

		if(l==r)

		{

			tl[0][x]=tr[0][x]=1,tl[1][x]=tr[1][x]=!((v[q[l]]>>a)&1);

			return ;

		}

		int mid=l+r>>1;

		build(l,mid,lson,a),build(mid+1,r,rson,a);

		pushup(x);

	}

	void updata(int l,int r,int x,int a,bool b)

	{

		if(l==r)

		{

			tl[0][x]=tr[0][x]=1,tl[1][x]=tr[1][x]=!b;

			return ;

		}

		int mid=l+r>>1;

		if(a<=mid)	updata(l,mid,lson,a,b);

		else	updata(mid+1,r,rson,a,b);

		pushup(x);

	}

	bool ql(int l,int r,int x,int a,int b,bool c)

	{

		if(a<=l&&r<=b)	return tl[c][x];

		int mid=l+r>>1;

		if(b<=mid)	return ql(l,mid,lson,a,b,c);

		if(a>mid)	return ql(mid+1,r,rson,a,b,c);

		return ql(mid+1,r,rson,a,b,ql(l,mid,lson,a,b,c));

	}

	bool qr(int l,int r,int x,int a,int b,bool c)

	{

		if(a<=l&&r<=b)	return tr[c][x];

		int mid=l+r>>1;

		if(b<=mid)	return qr(l,mid,lson,a,b,c);

		if(a>mid)	return qr(mid+1,r,rson,a,b,c);

		return qr(l,mid,lson,a,b,qr(mid+1,r,rson,a,b,c));

	}

}s[33];

inline int rd()

{

	int ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

void dfs1(int x)

{

	siz[x]=1;

	for(int i=head[x];i!=-1;i=next[i])

	{

		if(to[i]!=fa[x])

		{

			fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs1(to[i]),siz[x]+=siz[to[i]];

			if(siz[to[i]]>siz[son[x]])	son[x]=to[i];

		}

	}

}

void dfs2(int x,int tp)

{

	top[x]=tp,p[x]=++p[0],q[p[0]]=x;

	if(son[x])	dfs2(son[x],tp);

	for(int i=head[x];i!=-1;i=next[i])	if(to[i]!=fa[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);

}

void add(int a,int b)

{

	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;

}

void ask(int x,int y)

{

	unsigned int ret=0;

	int i;

	st[0]=0;

	while(top[x]!=top[y])

	{

		if(dep[top[x]]>=dep[top[y]])

		{

			for(i=0;i<k;i++)	ret=ret-(ret&(1<<i))+(s[i].qr(1,n,1,p[top[x]],p[x],(ret>>i)&1)<<i);

			x=fa[top[x]];

		}

		else	st[++st[0]]=y,y=fa[top[y]];

	}

	if(dep[x]<dep[y])	for(i=0;i<k;i++)	ret=ret-(ret&(1<<i))+(s[i].ql(1,n,1,p[x],p[y],(ret>>i)&1)<<i);

	else	for(i=0;i<k;i++)	ret=ret-(ret&(1<<i))+(s[i].qr(1,n,1,p[y],p[x],(ret>>i)&1)<<i);

	for(y=st[0];y;y--)	for(i=0;i<k;i++)	ret=ret-(ret&(1<<i))+(s[i].ql(1,n,1,p[top[st[y]]],p[st[y]],(ret>>i)&1)<<i);

	printf("%u\n",ret);

}

int main()

{

	n=rd(),m=rd(),k=rd();

	int i,j,a,b;

	for(i=1;i<=n;i++)	scanf("%u",&v[i]);

	memset(head,-1,sizeof(head));

	for(i=1;i<n;i++)	a=rd(),b=rd(),add(a,b),add(b,a);

	dep[1]=1,dfs1(1),dfs2(1,1);

	for(i=0;i<k;i++)	s[i].build(1,n,1,i);

	for(i=1;i<=m;i++)

	{

		scanf("%s",str);

		if(str[0]=='Q')	a=rd(),b=rd(),ask(a,b);

		else

		{

			a=rd(),scanf("%u",&v[a]);

			for(j=0;j<k;j++)	s[j].updata(1,n,1,p[a],(v[a]>>j)&1);

		}

	}

	return 0;

}//3 3 3 2 7 3  1 2 2 3 Query 2 3 Replace 1 3 Query 1 1

巴特西

【BZOJ2908】又是nand 树链剖分+线段树