NC24261. [USACO 2019 Feb G]Cow Land
描述
There are a total of N different attractions (2≤N≤10^5). Certain pairs of attractions are connected by pathways, N−1 in total, in such a way that there is a unique route consisting of various pathways between any two attractions. Each attraction ii has an integer enjoyment value ei, which can change over the course of a day, since some attractions are more appealing in the morning and others later in the afternoon.
A cow that travels from attraction i to attraction j gets to experience all the attractions on the route from i to j. Curiously, the total enjoyment value of this entire route is given by the bitwise XOR of all the enjoyment values along the route, including those of attractions i and j.
Please help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.
输入描述
The first line of input contains N and a number of queries Q (1≤Q≤10^5). The next line contains e1…eN (0≤ei≤10^9). The next N−1 lines each describe a pathway in terms of two integer attraction IDs a and b (both in the range 1…N). Finally, the last Q lines each describe either an update to one of the ei values or a query for the enjoyment of a route. A line of the form "1 i v" indicates that ei should be updated to value v, and a line of the form "2i j" is a query for the enjoyment of the route connecting attractions i and j.
In test data worth at most 50% of points, there will be no changes to the values of the attractions.
输出描述
For each query of the form "2 i j", print on a single line the enjoyment of the route from i to j.
示例1
输入:
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
C++(g++ 7.5.0) 解法, 执行用时: 242ms, 内存消耗: 20440K, 提交时间: 2023-05-18 00:27:32
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct HLD {
vector<int> siz, dep, fat, son, top, dfn, L, R;
HLD() {}
HLD(int rt, const vector<vector<int>> &g) { init(rt, g); }
void init(int rt, const vector<vector<int>> &g) {
assert(g.size() >= 2);
int n = g.size() - 1;
siz.assign(n + 1, 0);
dep.assign(n + 1, 0);
fat.assign(n + 1, 0);
son.assign(n + 1, 0);
top.assign(n + 1, 0);
dfn.assign(n + 1, 0);
L.assign(n + 1, 0);
R.assign(n + 1, 0);
function<void(int, int)> dfsA = [&](int u, int fa) {
siz[u] = 1;
dep[u] = dep[fa] + 1;
fat[u] = fa;
for (auto v : g[u]) {
if (v == fa) continue;
dfsA(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
};
dfsA(rt, 0);
int dfncnt = 0;
function<void(int, int)> dfsB = [&](int u, int tp) {
top[u] = tp;
dfn[++dfncnt] = u;
L[u] = dfncnt;
if (son[u]) dfsB(son[u], tp);
for (auto v : g[u]) {
if (v == fat[u] || v == son[u]) continue;
dfsB(v, v);
}
R[u] = dfncnt;
};
dfsB(rt, rt);
}
};
template<class T, class F>
class SegmentTree {
int n;
vector<T> node;
void update(int rt, int l, int r, int x, F f) {
if (r < x || x < l) return;
if (l == r) return node[rt] = f(node[rt]), void();
int mid = l + r >> 1;
update(rt << 1, l, mid, x, f);
update(rt << 1 | 1, mid + 1, r, x, f);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
}
T query(int rt, int l, int r, int x, int y) {
if (r < x || y < l) return T();
if (x <= l && r <= y) return node[rt];
int mid = l + r >> 1;
return query(rt << 1, l, mid, x, y) + query(rt << 1 | 1, mid + 1, r, x, y);
}
public:
SegmentTree(int _n = 0) { init(_n); }
SegmentTree(const vector<T> &src) { init(src); }
void init(int _n) {
n = _n;
node.assign(n << 2, T());
}
void init(const vector<T> &src) {
assert(src.size() >= 2);
init(src.size() - 1);
function<void(int, int, int)> build = [&](int rt, int l, int r) {
if (l == r) return node[rt] = src[l], void();
int mid = l + r >> 1;
build(rt << 1, l, mid);
build(rt << 1 | 1, mid + 1, r);
node[rt] = node[rt << 1] + node[rt << 1 | 1];
};
build(1, 1, n);
}
void update(int x, F f) { update(1, 1, n, x, f); }
T query(int x, int y) { return query(1, 1, n, x, y); }
};
const int N = 1e5 + 7;
int e[N];
vector<int> g[N];
HLD hld;
struct T {
int xsum = 0;
friend T operator+(const T &a, const T &b) { return { a.xsum ^ b.xsum }; }
};
struct F {
int upd;
T operator()(const T &x) { return { upd }; }
};
SegmentTree<T, F> sgt;
int path_query(int u, int v) {
auto &top = hld.top;
auto &dep = hld.dep;
auto &fat = hld.fat;
auto &L = hld.L;
int ans = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans ^= sgt.query(L[top[u]], L[u]).xsum;
u = fat[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans ^= sgt.query(L[u], L[v]).xsum;
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1;i <= n;i++) cin >> e[i];
for (int i = 1;i <= n - 1;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
hld.init(1, vector<vector<int>>(g, g + n + 1));
vector<T> e_src(n + 1);
for (int i = 1;i <= n;i++) e_src[hld.L[i]] = { e[i] };
sgt.init(e_src);
while (q--) {
int op;
cin >> op;
if (op == 1) {
int i, v;
cin >> i >> v;
sgt.update(hld.L[i], { v });
}
else {
int i, j;
cin >> i >> j;
cout << path_query(i, j) << '\n';
}
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 306ms, 内存消耗: 16984K, 提交时间: 2019-08-14 21:08:20
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=100010,INF=0x3f3f3f3f;
struct SegTree
{
int l,r,v;
#define ls(x) x << 1
#define rs(x) x << 1 | 1
#define l(x) tr[x].l
#define r(x) tr[x].r
#define v(x) tr[x].v
};
SegTree tr[maxn<<2];
vector<int> e[maxn];
int n,m,cnt,fa[maxn],dep[maxn],sz[maxn],son[maxn],dfn[maxn],seq[maxn],top[maxn],a[maxn];
void dfs1(int x,int fat)
{
sz[x]=1;
for(int i=0;i<(int)e[x].size();i++)
{
int to=e[x][i];
if(to==fat) continue;
fa[to]=x;
dep[to]=dep[x]+1;
dfs1(to,x) ;
if(sz[to]>sz[son[x]]) son[x]=to;
sz[x]+=sz[to] ;
}
}
void dfs2(int x,int tp)
{
dfn[x]=++cnt;
seq[cnt]=x;
top[x]=tp;
if(!son[x]) return;
dfs2(son[x],tp);
for(int i=0;i<(int)e[x].size();i++)
{
int to=e[x][i];
if(to==fa[x]||to==son[x]) continue;
dfs2(to,to);
}
}
void pushup(int x)
{
v(x)=v(ls(x))^v(rs(x));
}
void build(int x,int l,int r)
{
l(x)=l;
r(x)=r;
if(l==r)
{
v(x)=a[seq[l]];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
void modify(int x,int pos,int c)
{
if(l(x)==r(x))
{
v(x)=c;
return;
}
int mid=(l(x)+r(x))>>1;
if(pos<=mid) modify(ls(x),pos,c);
else modify(rs(x),pos,c);
pushup(x);
}
int query(int x,int l,int r)
{
if(l<=l(x)&&r(x)<=r) return v(x);
int mid=(l(x)+r(x))>>1,ans=0;
if(l<=mid) ans^=query(ls(x),l,r);
if(mid<r) ans^=query(rs(x),l,r);
return ans;
}
int Query(int x,int y)
{
int fx=top[x],fy=top[y],ans=0;
while(fx!=fy)
{
if(dep[fx]<dep[fy])
{
swap(x,y);
swap(fx,fy);
}
ans^=query(1,dfn[fx],dfn[x]);
x=fa[fx];
fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);
return ans^query(1,dfn[x],dfn[y]);
}
int main()
{
scanf("%d%d",&n,&m) ;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b) ;
e[a].push_back(b);
e[b].push_back(a);
}
dfs1(1,-1);
dfs2(1,1);
build(1,1,n);
while(m--)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1) modify(1,dfn[x],y) ;
else printf("%d\n",Query(x,y));
}
return 0 ;
}
C++(clang++ 11.0.1) 解法, 执行用时: 229ms, 内存消耗: 14116K, 提交时间: 2022-10-23 12:24:41
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define N 100005
int n,m,a[N],sum[4*N];
int f[N],d[N],siz[N],son[N],top[N],rk[N],id[N],cnt;//树链剖分
vector<int> G[N];
void dfs1(int u,int fa,int depth){
f[u] = fa;
d[u] = depth;
siz[u] = 1;
for (int v : G[u]){
if (v == fa) continue;
dfs1(v,u,depth+1);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u,int t){
top[u] = t;
id[u] = ++cnt;
rk[cnt] = u;
if (!son[u]) return ;
dfs2(son[u],t);
for (int v : G[u]){
if (v != son[u] && v != f[u]) dfs2(v,v);
}
}
void update(int x,int val,int l,int r,int rt){
if (l == r){
sum[rt] = val;
return ;
}
int m = (l+r)>>1;
if (x <= m) update(x,val,l,m,rt<<1);
else update(x,val,m+1,r,rt<<1|1);
sum[rt] = sum[rt<<1]^sum[rt<<1|1];
}
int query(int L,int R,int l,int r,int rt){
if (l > R || r < L) return 0;
if (l >= L && r <= R) return sum[rt];
int m = (l+r)>>1;
return query(L,R,l,m,rt<<1)^query(L,R,m+1,r,rt<<1|1);
}
int sumTree(int x,int y){//计算x到y路径的异或和
int ans = 0;
while (top[x] != top[y]){
if(d[top[x]] > d[top[y]]) swap(x,y);
ans ^= query(id[top[y]],id[y],1,n,1);
y = f[top[y]];
}
if (d[x] > d[y]) swap(x,y);
ans ^= query(id[x],id[y],1,n,1);
return ans;
}
int main(void){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++){
int u,v; cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs1(1,0,0);
dfs2(1,1);
for (int i = 1; i <= n ; i++) update(id[i],a[i],1,n,1);
while (m--){
int op,x,y; cin >> op >> x >> y;
if (op == 1){
update(id[x],y,1,n,1);
}else{
cout << sumTree(x,y) << "\n";
}
}
return 0;
}