列表

详情

NC205397. 异或Tree

描述


前置定义：（牛逼值）

给定一个长度为n的数组：，该数组的牛逼值为：。其中表示异或运算，与传统异或运算定义一致。

例如长度为3的数组：，那么他的牛逼值为：

=10。

题面：

lt是一个三维生物，他掌管着二维世界的运行规律，某一天他发现一颗有个节点的无根树，该树只有点权，没有边权，现在他要进行次操作，每次进行以下两种操作之一：

  1. 选择一个节点，将其点权进行修改。
  2. 给出参数u,v，询问u->v的简单路径上的所有点按顺序组成一个数组，计算这个数组的牛逼值。

输入描述

单组输入。
第一行输入n,m，代表树的节点个数，以及进行的操作次数，保证。
第二行输入n个正整数，代表每个节点的点权，保证输入值。
接下来n-1行，每行两个正整数u,v，表示节点与节点之间有一条双向边，保证输入规模为一颗树，且1<=u,v<=n且u!=v。
接下来m行，每行三个数字id,u,v，保证1<=id<=2。
若id=1，则表示是第一种操作，此时，将节点u的点权修改为v。
若id=2，则表示是第二种操作1<=u,v<=n，此时，你需要输出该次询问结果。

输出描述

对于每个第二种操作输出一行，表示该次询问的结果。
保证64位整数可以存下结果

示例1

输入: 

3 3
1 2 4
1 2
1 3
2 2 3
1 1 8
2 2 3

输出: 

22
50

说明:


对于第一次询问，节点2->节点3的简单路径上所有点权按顺序组成的数组是{2,1,4}
牛逼值=2+1+4+(2^1)+(2^1^4)+(1^4)=22。

第二次操作，将节点1的点权修改为8。

第三次的询问操作，组成的数组为{2,8,4}
牛逼值=2+8+4+(2^8)+(2^8^4)+(8^4)=50

示例2

输入: 

10 10
4 3 1 1 6 1 6 2 8 10 
1 2
2 3
2 4
4 5
5 6
3 7
3 8
2 9
9 10
1 4 1
2 10 5
1 2 9
1 9 10
2 5 4
2 1 1
2 1 9
1 8 8
2 2 6
2 6 2

输出: 

83
14
4
46
74
74

说明:

一组友好的帮助debug的大样例

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 722ms, 内存消耗: 42360K, 提交时间: 2020-05-25 23:28:02 

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 5e4 + 5;
const ll LINF = 1e18 + 5;
constexpr int mod = 1e9 + 7;
int n, m, a[N], b[N];
vector<int> G[N];
int sz[N], top[N], son[N], dep[N], fa[N], dfn[N], idfn[N], tot; 
int cnt[32], cnt1[32], cnt2[32];
namespace SegTree
{
	#define ls (p<<1)
	#define rs (p<<1|1)
	struct seg
	{
		int l, r;
		int sum[32], tag[32];
	}t[N<<2];
	void pushup(int p)
	{
		for(int i=0; i<30; i++) t[p].sum[i] = t[ls].sum[i] + t[rs].sum[i];
	}
	void setval(int p, int i)
	{
		t[p].sum[i] = t[p].r - t[p].l + 1 - t[p].sum[i];
		t[p].tag[i] ^= 1;
	}
	void pushdown(int p)
	{
		for(int i=0; i<30; i++)
			if(t[p].tag[i])
			{
				setval(ls, i); setval(rs, i);
				t[p].tag[i] = 0;
			}
	}
	void build(int p, int l, int r)
	{
		t[p].l = l, t[p].r = r;
		if(l==r) 
		{
			for(int i=0; i<30; i++)
				t[p].sum[i] = (a[idfn[l]]>>i)&1;
			return;
		}
		int mid = (l+r)>>1;
		build(ls, l, mid); build(rs, mid+1, r);
		pushup(p);
	}
	void upd(int p, int x, int y, int v)
	{
		int l = t[p].l, r = t[p].r;
		if(l>=x && r<=y) 
		{
			for(int i=0; i<30; i++)
				if((v>>i)&1) setval(p, i);
			return;
		}
		pushdown(p);
		int mid = (l+r)>>1;
		if(x<=mid) upd(ls, x, y, v);
		if(y>mid) upd(rs, x, y, v);
		pushup(p);
	}
	void ask(int p, int x, int y)
	{
		int l = t[p].l, r = t[p].r;
		if(l>=x && r<=y) 
		{
			for(int i=0; i<30; i++) cnt[i] += t[p].sum[i];
			return;
		}
		pushdown(p);
		int mid = (l+r)>>1;
		if(x<=mid) ask(ls, x, y);
		if(y>mid) ask(rs, x, y);
	}
	#undef ls
	#undef rs
}
using namespace SegTree;
void dfs1(int u, int f) 
{
	dep[u] = dep[f] + 1; fa[u] = f;
	sz[u] = 1;
	a[u] ^= a[f];
	for(int v : G[u])
	{
		if(v!=f)
		{
			dfs1(v, u);
			sz[u] += sz[v];
			if(sz[v]>sz[son[u]]) son[u] = v;
		}
	}
}
void dfs2(int u, int t) 
{
	top[u] = t;
	dfn[u] = ++tot;
	idfn[tot] = u;
	if(!son[u]) return;
	dfs2(son[u], t);
	for(int v : G[u])
		if(v!=son[u]&&v!=fa[u]) dfs2(v, v);
}
int LCA(int x, int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}
void askt(int x, int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		ask(1, dfn[top[x]], dfn[x]); 
		x = fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ask(1, dfn[x], dfn[y]);
}
int main()
{	
	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++) scanf("%d", a+i), b[i] = a[i];
	for(int i=1; i<n; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].pb(v); G[v].pb(u);
	}
	dfs1(1, 0); dfs2(1, 1);
	build(1, 1, n);
	for(int i=1; i<=m; i++)
	{
		int op, u, v;
		scanf("%d%d%d", &op, &u, &v);
		if(op==1) 
		{
			upd(1, dfn[u], dfn[u]+sz[u]-1, b[u]^v);
			b[u] = v;
		}
		else
		{
			int w = LCA(u, v);
			for(int i=0; i<30; i++) cnt[i] = 0;
			askt(u, w);
			memcpy(cnt1, cnt, sizeof(cnt));
			for(int i=0; i<30; i++) cnt[i] = 0;
			askt(v, w);
			memcpy(cnt2, cnt, sizeof(cnt));
			ll ans = 0;
			for(int i=0; i<30; i++)
			{
				int x = cnt1[i], y = cnt2[i];
				int xx = dep[u] - dep[w] + 1 - x, yy = dep[v] - dep[w] + 1 - y;
				ll cur = 1ll*x*xx+1ll*y*yy;
				if((b[w]>>i)&1) cur += 1ll*x*y + 1ll*xx*yy;		
				else cur += 1ll*x*yy + 1ll*xx*y;
				ans += cur*(1<<i);
			}
			printf("%lld\n", ans);
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 455ms, 内存消耗: 106724K, 提交时间: 2020-05-26 12:23:40 

#include<bits/stdc++.h>
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define M(x) ((T[x].l+T[x].r)>>1)
using namespace std;
typedef long long ll;
const int N=5e4+11,M=31;
typedef long long ll;
struct Tree{
	int l,r,len;
	int sum[M],lj[M],rj[M],cnt[M];
	Tree(){
		l=r=len=0;
		for(int i=0;i<M;i++) sum[i]=lj[i]=rj[i]=cnt[i]=0;
	} 
}T[N<<2];
int a[N],b[N];
Tree merge(Tree &ll,Tree &rr){
	Tree ans;
	ans.l=ll.l;ans.r=rr.r; 
	for(int i=0;i<M;i++){
		ans.sum[i]=ll.sum[i]+rr.sum[i];
		ans.sum[i]+=ll.rj[i]*(rr.len-rr.lj[i]);
		ans.sum[i]+=rr.lj[i]*(ll.len-ll.rj[i]);
		if(ll.cnt[i]&1) ans.lj[i]=ll.lj[i]+(rr.len-rr.lj[i]);
		else ans.lj[i]=ll.lj[i]+rr.lj[i];
		if(rr.cnt[i]&1) ans.rj[i]=rr.rj[i]+(ll.len-ll.rj[i]);
		else ans.rj[i]=rr.rj[i]+ll.rj[i];
		ans.cnt[i]=ll.cnt[i]+rr.cnt[i];
		
	}
	ans.len=ll.len+rr.len;
	return ans;
}
void build(int x,int l,int r){
	T[x].l=l;T[x].r=r;
	if(l==r){
		T[x].len=1;
		for(int i=0;i<M;i++){
			T[x].sum[i]=T[x].lj[i]=T[x].rj[i]=T[x].cnt[i]=((b[l]>>i)&1);
		}
		return ;
	}
	build(L(x),l,M(x));
	build(R(x),M(x)+1,r);
	T[x]=merge(T[L(x)],T[R(x)]);
	return ;
}
void updata(int x,int pos,int val){
	if(T[x].l==pos&&T[x].r==pos){
		for(int i=0;i<M;i++){
			T[x].sum[i]=T[x].lj[i]=T[x].rj[i]=T[x].cnt[i]=((val>>i)&1);
		}
		return ;
	}
	if(pos<=M(x)) updata(L(x),pos,val);
	else updata(R(x),pos,val);
	T[x]=merge(T[L(x)],T[R(x)]);
	return ;
}
Tree query(int x,int l,int r){
	if(l<=T[x].l&&r>=T[x].r) return T[x];
	if(r<=M(x)) return query(L(x),l,r);
	else if(l>M(x)) return query(R(x),l,r);
	else{
		Tree ll=query(L(x),l,r),rr=query(R(x),l,r);
		return merge(ll,rr);
	}
}
//上面为线段树 
struct Side{
	int v,ne;
}S[N<<1];
char op[18];
int sn,head[N],tn,tid[N],size[N],dep[N];
int top[N],fa[N],son[N];
void initS(int n){
	sn=tn=0;
	for(int i=0;i<=n;i++){
		fa[i]=son[i]=0;
		size[i]=1;
		dep[i]=1;
		head[i]=-1;
	}
}
void addS(int u,int v){
	S[sn].v=v;
	S[sn].ne=head[u];
	head[u]=sn++;
}
void dfs1(int u){
	for(int i=head[u];~i;i=S[i].ne){
		int v=S[i].v;
		if(v==fa[u]) continue;
		fa[v]=u;
		dep[v]=dep[u]+1;
		dfs1(v);
		size[u]+=size[v];
		if(size[v]>=size[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tf){
	tid[u]=++tn;
	b[tn]=a[u];
	top[u]=tf;
	if(!son[u]) return ;
	dfs2(son[u],tf);
	for(int i=head[u];i!=-1;i=S[i].ne){
		int v=S[i].v;
		if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
	}
}
Tree querypath(int x,int y){
	int flag=1; 
	Tree ans1,ans2,temp;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			flag^=1;
			swap(x,y);
		}
		temp=query(1,tid[top[x]],tid[x]);
		if(flag){
			for(int i=0;i<M;i++) swap(temp.lj[i],temp.rj[i]);
			ans1=merge(ans1,temp);
		}else ans2=merge(temp,ans2);
		x=fa[top[x]];
	}
	flag^=1;
	if(dep[x]>dep[y]){
		swap(x,y);
		flag^=1;
	}
	temp=query(1,tid[x],tid[y]);
	if(flag){
		for(int i=0;i<M;i++) swap(temp.lj[i],temp.rj[i]);
		ans1=merge(ans1,temp);
	}else ans2=merge(temp,ans2);
	ans1=merge(ans1,ans2);
	return ans1;
}
int main(){
	int t,n,m,op,u,v;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	initS(n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		addS(u,v);
		addS(v,u);
	}
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		scanf("%d%d%d",&op,&u,&v);
		if(op==1) updata(1,tid[u],v);
		else{
			Tree ans=querypath(u,v);
			ll res=0;
			for(int i=M-1;i>=0;i--) res=((res<<1ll)+ans.sum[i]);
			printf("%lld\n",res);
		}
	}
	return 0;
}
//3 3
//1 2 3
//1 2
//1 3
//2 2 3
//1 1 2
//2 1 1

上一题

© 2024 nowcoder.com