刷题记录:牛客NC24261[USACO 2019 Feb G]Cow Land

传送门:牛客

题目描述

Cow Land 总共有 $N$ 个不同的景点（ $2\le N\le 10^5$ ）。 一共有 $n-1$ 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。
每个景点 $i$ 都有一个享受值 $e_i$ ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。
从景点 $i$ 到景点 $j$ 的奶牛们可以欣赏从景点 $i$ 到景点 $j$ 的路上的所有景观。这条路线的享受值为景点 $i$ 到景点 $j$ 的路上的所有景点（包括景点 $i$ 和景点 $j$ ）的享受值按位进行异或运算的结果。
请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

输入:
5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3
输出:
21
20
4
20

一道维护树上区间异或的题目

首先是对树上进行区间异或,所以此时我们需要使用树链剖分将树形结构分解为线性结构,那么此时我们的问题就变成了如何对一个区间的区间异或值进行维护

其实呢,这道题除了树链剖分操作之外的操作和这道题基本上时一样的.可以先去做做那道题再来做本题

简单来说,也就是对于一个区间来说,我们不能直接使用线段树来维护区间异或和,但是我们可以使用线段树来维护区间每一个位的二进制位1的总数(因为0并不影响异或结果).也就是说对于每一个数字,我们都将其二进制化,然后求一下每一个区间每一个二进制位的1的总数即可.对于最终的答案,既然我们已经知道了每一个二进制位1的个数,对于二进制位1的个数为偶数的位置,此时我们异或的最终结果肯定是0,反之则为1.然后我们再求一下最终异或出来的二进制转化为十进制即可

但是牛客上给的内存十分的少,可能是爬题的时候遗留下来的问题,所以对于我的代码会导致MLE,但是洛谷上是可以轻松AC的,可能是因为这个原因导致牛客上AC的代码极少

下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 100007
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int fa[maxn],Size[maxn],max_son[maxn],dep[maxn];
vector<int>edge[maxn];
void dfs1(int u,int per_u) {Size[u]=1;for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==per_u) continue;dep[v]=dep[u]+1;dfs1(v,u);fa[v]=u;Size[u]+=Size[v];if(Size[v]>Size[max_son[u]]) {max_son[u]=v;}}
}
int top[maxn],id[maxn],rev[maxn],tot=0;
void dfs2(int u,int t) {top[u]=t;id[u]=++tot;rev[tot]=u;if(!max_son[u]) return ;dfs2(max_son[u],t);for(int i=0;i<edge[u].size();i++) {int v=edge[u][i];if(v==fa[u]||v==max_son[u]) continue;dfs2(v,v);}
}
struct Segment_tree{int l,r,bit1[33];
}tree[maxn*4];int w[maxn];
void pushup(int rt) {for(int i=1;i<=32;i++) {tree[rt].bit1[i]=tree[ls].bit1[i]+tree[rs].bit1[i];}
} 
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {int num=w[rev[l]];for(int i=1;i<=32;i++) {tree[rt].bit1[i]=num&1;if(num) num>>=1;}return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
void update(int pos,int rt,int val) {if(tree[rt].l==pos&&tree[rt].r==pos) {int num=val;for(int i=1;i<=32;i++) {tree[rt].bit1[i]=num&1;if(num) num>>=1;}return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(pos<=mid) update(pos,ls,val);else update(pos,rs,val);pushup(rt);
}
int ans[33];
void query(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {for(int i=1;i<=32;i++) {ans[i]+=tree[rt].bit1[i];}return ;}int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) query(l,r,ls);else if(l>mid) query(l,r,rs);else query(l,mid,ls),query(mid+1,r,rs);
}
int get_num() {int Ans=0;for(int i=1;i<=32;i++) {if(ans[i]&1) ans[i]=1;else ans[i]=0;}int k=1;for(int i=1;i<=32;i++) {Ans+=ans[i]*k;k*=2;}return Ans;
}
int ask(int u,int v) {memset(ans,0,sizeof(ans));while(top[u]!=top[v]) {if(dep[top[u]]<dep[top[v]]) swap(u,v);query(id[top[u]],id[u],1);u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);query(id[u],id[v],1);return get_num();
}
int n,q;
int main() {n=read();q=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=1;i<=n-1;i++) {int u=read(),v=read();edge[u].push_back(v);edge[v].push_back(u);}dfs1(1,0);dfs2(1,1);build(1,tot,1);for(int i=1;i<=q;i++) {int opt=read();if(opt==1) {int u=read(),val=read();update(id[u],1,val);}else {int u=read(),v=read();printf("%d\n",ask(u,v));}}return 0;
}