记录编号	88962	评测结果	AAAAAAAAAA
题目名称	zwei	最终得分	100
用户昵称	超级傲娇的AC酱	是否通过	通过
代码语言	C++	运行时间	2.010 s
提交时间	2014-02-26 19:31:38	内存使用	0.31 MiB

#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
struct SgTree
{
	int L,R;
	SgTree *LeftChild,*RightChild;
	int val;
};
SgTree *Root=new SgTree;
SgTree *ConstNode=new SgTree;
int VISIT(int,int,SgTree *);
void CHANGE(int,int,SgTree *);
void BUILD(int,int,SgTree *);
vector<int>A;
int main()
{
	freopen("zwei.in","r",stdin);
	freopen("zwei.out","w",stdout);
	int i,j,n,m,x,y,z;
	cin>>n>>m;
	A.resize(n);
	for(i=0;i<n;i++)
		cin>>A[i];
	BUILD(0,n-1,Root);
	for(i=0;i<m;i++){
		cin>>x>>y>>z;
		if(x==0)CHANGE(y-1,z,Root);
		if(x==1)cout<<VISIT(y-1,z-1,Root)<<endl;
	}
	return 0;
}
void BUILD(int l,int r,SgTree *Node)
{
	Node->L=l;Node->R=r;
	if(l==r)
	{
		Node->LeftChild=ConstNode;
		Node->RightChild=ConstNode;
		Node->val=A[l];
	}
	else
	{
		Node->LeftChild=new SgTree;
		Node->RightChild=new SgTree;
		BUILD(l,(l+r)/2,Node->LeftChild);
		BUILD((l+r)/2+1,r,Node->RightChild);
		Node->val=Node->LeftChild->val^Node->RightChild->val;
	}
}
void CHANGE(int pos,int num,SgTree *Node)
{
	if(pos==Node->L&&pos==Node->R)
		Node->val=num;
	else
	{
		if(pos<=(Node->L+Node->R)/2)
			CHANGE(pos,num,Node->LeftChild);
		if(pos>(Node->L+Node->R)/2)
			CHANGE(pos,num,Node->RightChild);
		Node->val=Node->LeftChild->val^Node->RightChild->val;
	}
}
int VISIT(int l,int r,SgTree *Node)
{
	if(l==Node->L&&r==Node->R)
		return Node->val;
	else
	{
		if(l>(Node->L+Node->R)/2)
			return VISIT(l,r,Node->RightChild);
		if(r<=(Node->L+Node->R)/2)
			return VISIT(l,r,Node->LeftChild);
		if(l<=(Node->L+Node->R)/2&&(Node->L+Node->R)/2<r)
			return VISIT(l,(Node->L+Node->R)/2,Node->LeftChild)^VISIT((Node->L+Node->R)/2+1,r,Node->RightChild);
	}
}