2019ICPC西安邀请赛E题，线段树+述链剖分+nim博弈Tree

89 阅读 0 评论 59 点赞

我是靠谱客的博主着急鲜花，这篇文章主要介绍2019ICPC西安邀请赛E题，线段树+述链剖分+nim博弈Tree，现在分享给大家，希望可以做个参考。

Tree

https://nanti.jisuanke.com/t/39272
题意：给你一颗树，结点权值告诉你，你有如下三种操作
1 s t 修改从1到s的路径上的所有点，a[i]=a[i]|t
2 s t 修改从1到s的路径上的所有点，a[i]=a[i]&t
3 s t 询问将1到s的路径上的所有点作为石头堆，再加上一个个数为t的石头堆，进行一次尼姆(nim)博弈，先手胜利输出YES，否则输出NO

前置知识：
nim博弈先手的必胜条件为，n堆石头的异或和不为0,也即a[1] ^ a[2] ^a[3] . . .^a[n]!=0
所以问题就转为了a[1] ^ a[2] ^ a[] . . .^ a[s] ^ a[t]是否为0，为0输出YES，否则输出NO

分析：这道题的1，2操作是对树上的一条链进行|，&操作，所以需要用到树链剖分，并且用线段树去维护异或和，对于所有数的二进制的每一位，我们都需要开一颗线段树去维护，这里数最大1e9，所以二进制位最多31位，我们需要开31一颗线段树去分别维护即可.

AC代码：

复制代码

#include<bits/stdc++.h>
#define ls dep<<1
#define rs dep<<1|1
using namespace std;
const int Maxn = 1e5+10;
struct Edge{
int v;
int next;
}edge[Maxn*2];
int head[Maxn];
int fa[Maxn];
int siz[Maxn];
int son[Maxn];
int dep[Maxn];
int dfn[Maxn];
int top[Maxn];
int a[Maxn];
int tim=0;
int sum[31][Maxn*4]={0};//线段树区间和 
int lz[31][Maxn*4]={0};//延迟标记
int cnt = 0;
int N,M;
void init(){
memset(head,-1,sizeof(head));
return ;
}
void build(int u,int v){
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
edge[++cnt].v = u;
edge[cnt].next = head[v];
head[v] = cnt;
return ;
}
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
siz[u] = 1;
int maxsonsize = -1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxsonsize){
maxsonsize = siz[v];
son[u] = v;
}
}
return ;
}
void dfs2(int u,int t){
dfn[u] = ++tim;
top[u] = t;
if(!son[u]) return ;
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
return ;
}
void pushup(int pos,int dep){
sum[pos][dep] = sum[pos][ls]+sum[pos][rs];
return ;
}
void pushdown(int pos,int dep,int l,int r){
if(lz[pos][dep]==-1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=-1;
sum[pos][ls]=sum[pos][rs] = 0;
lz[pos][dep] = 0;
}
else if(lz[pos][dep]==1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=1;
sum[pos][ls]=(mid-l+1);
sum[pos][rs]=(r-mid);
lz[pos][dep] = 0;
}
return ;
}
void modify(int pos,int l,int r,int ql,int qr,int dep,int val){
if(ql<=l&&r<=qr){
if(val==-1) sum[pos][dep] = 0;
else sum[pos][dep] = (r-l+1);
lz[pos][dep] = val;
return ;
}
pushdown(pos,dep,l,r);
int mid = l+r>>1;
if(ql<=mid) modify(pos,l,mid,ql,qr,ls,val);
if(qr>mid) modify(pos,mid+1,r,ql,qr,rs,val);
pushup(pos,dep);
return ;
}
void mchain(int pos,int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(pos,1,N,dfn[top[x]],dfn[x],1,val);
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
modify(pos,1,N,dfn[x],dfn[y],1,val);
return ;
}
int query(int pos,int l,int r,int ql,int qr,int dep){
if(ql<=l&&r<=qr){
return sum[pos][dep];
}
pushdown(pos,dep,l,r);
int ans = 0;
int mid = l+r>>1;
if(ql<=mid) ans+=query(pos,l,mid,ql,qr,ls);
if(qr>mid)
ans+=query(pos,mid+1,r,ql,qr,rs);
pushup(pos,dep);
return ans;
}
int qchain(int pos,int x,int y){
int ans = 0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(pos,1,N,dfn[top[x]],dfn[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(pos,1,N,dfn[x],dfn[y],1);
return ans;
}
bool check(int pos,int val,int s){
int ans = qchain(pos,1,s);
ans&=1;
if(ans&&val) return true;
if(!ans&&!val) return true;
return false;
}
int main(){
init();
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<N;i++){
int u,v;
scanf("%d %d",&u,&v);
build(u,v);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=N;i++){
for(int k=0;k<31;k++){
int val = (1<<k)&a[i];
if(val) modify(k,1,N,dfn[i],dfn[i],1,1);
}
}
while(M--){
int op,s,t;
scanf("%d %d %d",&op,&s,&t);
if(op==1){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(val) mchain(i,1,s,1);
}
}
else if(op==2){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!val) mchain(i,1,s,-1);
}
}
else{
int flag = 1;
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!check(i,val,s)){
flag = 0;
break;
}
}
if(!flag) printf("YESn");
else printf("NOn");
}
}
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include<bits/stdc++.h>
#define ls dep<<1
#define rs dep<<1|1
using namespace std;
const int Maxn = 1e5+10;
struct Edge{
int v;
int next;
}edge[Maxn*2];
int head[Maxn];
int fa[Maxn];
int siz[Maxn];
int son[Maxn];
int dep[Maxn];
int dfn[Maxn];
int top[Maxn];
int a[Maxn];
int tim=0;
int sum[31][Maxn*4]={0};//线段树区间和 
int lz[31][Maxn*4]={0};//延迟标记
int cnt = 0;
int N,M;
void init(){
memset(head,-1,sizeof(head));
return ;
}
void build(int u,int v){
edge[++cnt].v = v;
edge[cnt].next = head[u];
head[u] = cnt;
edge[++cnt].v = u;
edge[cnt].next = head[v];
head[v] = cnt;
return ;
}
void dfs1(int u,int f){
fa[u] = f;
dep[u] = dep[f]+1;
siz[u] = 1;
int maxsonsize = -1;
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>maxsonsize){
maxsonsize = siz[v];
son[u] = v;
}
}
return ;
}
void dfs2(int u,int t){
dfn[u] = ++tim;
top[u] = t;
if(!son[u]) return ;
dfs2(son[u],t);
for(int i=head[u];i!=-1;i=edge[i].next){
int v = edge[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
return ;
}
void pushup(int pos,int dep){
sum[pos][dep] = sum[pos][ls]+sum[pos][rs];
return ;
}
void pushdown(int pos,int dep,int l,int r){
if(lz[pos][dep]==-1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=-1;
sum[pos][ls]=sum[pos][rs] = 0;
lz[pos][dep] = 0;
}
else if(lz[pos][dep]==1){
int mid = l+r>>1;
lz[pos][ls]=lz[pos][rs]=1;
sum[pos][ls]=(mid-l+1);
sum[pos][rs]=(r-mid);
lz[pos][dep] = 0;
}
return ;
}
void modify(int pos,int l,int r,int ql,int qr,int dep,int val){
if(ql<=l&&r<=qr){
if(val==-1) sum[pos][dep] = 0;
else sum[pos][dep] = (r-l+1);
lz[pos][dep] = val;
return ;
}
pushdown(pos,dep,l,r);
int mid = l+r>>1;
if(ql<=mid) modify(pos,l,mid,ql,qr,ls,val);
if(qr>mid) modify(pos,mid+1,r,ql,qr,rs,val);
pushup(pos,dep);
return ;
}
void mchain(int pos,int x,int y,int val){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
modify(pos,1,N,dfn[top[x]],dfn[x],1,val);
x = fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
modify(pos,1,N,dfn[x],dfn[y],1,val);
return ;
}
int query(int pos,int l,int r,int ql,int qr,int dep){
if(ql<=l&&r<=qr){
return sum[pos][dep];
}
pushdown(pos,dep,l,r);
int ans = 0;
int mid = l+r>>1;
if(ql<=mid) ans+=query(pos,l,mid,ql,qr,ls);
if(qr>mid)
ans+=query(pos,mid+1,r,ql,qr,rs);
pushup(pos,dep);
return ans;
}
int qchain(int pos,int x,int y){
int ans = 0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=query(pos,1,N,dfn[top[x]],dfn[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
ans+=query(pos,1,N,dfn[x],dfn[y],1);
return ans;
}
bool check(int pos,int val,int s){
int ans = qchain(pos,1,s);
ans&=1;
if(ans&&val) return true;
if(!ans&&!val) return true;
return false;
}
int main(){
init();
scanf("%d %d",&N,&M);
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<N;i++){
int u,v;
scanf("%d %d",&u,&v);
build(u,v);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=N;i++){
for(int k=0;k<31;k++){
int val = (1<<k)&a[i];
if(val) modify(k,1,N,dfn[i],dfn[i],1,1);
}
}
while(M--){
int op,s,t;
scanf("%d %d %d",&op,&s,&t);
if(op==1){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(val) mchain(i,1,s,1);
}
}
else if(op==2){
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!val) mchain(i,1,s,-1);
}
}
else{
int flag = 1;
for(int i=0;i<31;i++){
int val = (1<<i)&t;
if(!check(i,val,s)){
flag = 0;
break;
}
}
if(!flag) printf("YESn");
else printf("NOn");
}
}
return 0;
}