「BZOJ4811」[Ynoi2017]由乃的OJ

Description

经元是一个有nn个点的树,每个点的包括一个位运算opt和一个权值xx,位运算有&,l,^三种,分别用11,22,33表示。
为了治疗失眠,Deus可以将一些神经递质放在点xx上,初始的刺激值是v0v_0。然后vv依次经过从xxyy的所有节点,每经过一个点iivv就变成voptixiv opt_i xi,所以他想问你,最后到yy时,希望得到的刺激值尽可能大,所以最大值的vv可以是多少呢?当然由于初始的神经递质的量有限,所以给定的初始值必须是在[0,z][0,z]之间。Deus每次都会给你33个数,x,y,zx,y,z

Input

第一行三个数nnmmkkkk的意义是每个点上的数,以及询问中的数值zz<2k<2^k。之后n行
每行两个数x,yx,y表示该点的位运算编号以及数值
之后n1n - 1行,每行两个数x,yx,y表示xxyy之间有边相连
之后mm行,每行四个数,Q,x,y,zQ,x,y,z表示这次操作为QQ(11位询问,22为修改),x,y,zx,y,z意义如题所述
0n,m100000,k640 \leq n , m \leq 100000 , k \leq 64

Output

对于每个操作11,输出到最后可以造成的最大刺激度vv

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
5 5 3
1 7
2 6
3 7
3 6
3 1
1 2
2 3
3 4
1 5
1 1 4 7
1 1 3 5
2 1 1 3
2 3 3 3
1 1 3 2

Sample Output

1
2
3
7
1
5

Solution

由于位运算不支持结合律,所以就…
fi,jf_{i,j}表示第ii位的初始值是jj,经过变化之后的得到的之后。区间之间是可以合并的。

force

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 110000;
int n, m, k;
struct Edge {
int u, v, nxt;
}e[N * 2];
struct T {
bool s[70][2];
bool t[70][2];
void init() {
for(int i = 63;~i; --i)
t[i][0] = s[i][0] = 0, t[i][1] = s[i][1] = 1;
}
}t[N * 4];
int head[N], en;
T mov(T &s, T &t) {
T tmp;
for(int i = 63; ~i; --i)
for(int j = 0; j < 2; ++j)
tmp.s[i][j] = t.s[i][s.s[i][j]];
for(int i = 63; ~i; --i)
for(int j = 0; j < 2; ++j)
tmp.t[i][j] = s.t[i][t.t[i][j]];
return tmp;
}
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int son[N], siz[N], fa[N], d[N];
void dfs1(int x, int F) {
siz[x] = 1;
fa[x] = F;
d[x] = d[F] + 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs1(y, x);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
int top[N], num, id[N];
unsigned long long a[N], op[N];
unsigned long long b[N], opt[N];
void dfs2(int x, int F) {
id[x] = ++num;
b[id[x]] = a[x];
opt[id[x]] = op[x];
top[x] = F;
if(!son[x]) return;
dfs2(son[x], F);
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int ls[N * 4], rs[N * 4];
#define lch (o<<1)
#define rch (o<<1|1)
int cal(int v, int op, int x) {
if(op == 1) return v & x;
if(op == 2) return v | x;
return v ^ x;
}
void up(int o) {
t[o] = mov(t[lch], t[rch]);
}
void build(int o, int l, int r) {
ls[o] = l, rs[o] = r;
if(l == r) {
for(int i = 63; ~i; --i)
for(int j = 0; j < 2; ++j)
t[o].t[i][j] = t[o].s[i][j] = cal((b[l] >> i) & 1, opt[l], j);
return ;
}
int mid = (l +r) >>1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
up(o);
}
void ins(int o, int x, int op, unsigned long long val) {
if(ls[o] == rs[o]) {
for(int i = 63; ~i; --i)
for(int j = 0; j < 2; ++j)
t[o].t[i][j] = t[o].s[i][j] = cal((val >> i) & 1, op, j);
return;
}
int mid = (ls[o] + rs[o]) >> 1;
if(x <= mid) ins(lch, x, op, val);
else ins(rch, x, op, val);
up(o);
}
T ask(int o, int l, int r) {
if(l <= ls[o] && r >= rs[o])
return t[o];
int mid = (ls[o] + rs[o]) >> 1;
if(r <= mid) return ask(lch, l, r);
if(l > mid) return ask(rch, l, r);
T lt = ask(lch, l, r);
T rt = ask(rch, l, r);
return mov(lt, rt);
}
unsigned long long query(int x, int y, unsigned long long z) {
bool cj = 0;
T t1, t2, res, tmp;
t1.init();
t2.init();
res.init();
while(top[x] != top[y]) {

if(d[top[x]] < d[top[y]]) swap(x, y), swap(t1, t2), cj ^= 1;
tmp = ask(1, id[top[x]], id[x]);
t1 = mov(tmp, t1);
x = fa[top[x]];
}
if(d[x] > d[y]) swap(t1, t2), swap(x, y), cj ^= 1;
tmp = ask(1, id[x], id[y]);
t2 = mov(tmp, t2);
if(cj) swap(t1, t2);
for(int i = 64;~i; --i)
for(int j = 0; j < 2; ++j)
res.s[i][j] = t2.s[i][t1.t[i][j]];
unsigned long long ans = 0;
unsigned long long c = 0;
for(int i = 63; ~i; --i) {
if(res.s[i][0] == 1) {
ans ^= (1ull << i);
} else if((c + (1ull << i)) <= z && res.s[i][1] == 1) {
ans ^= (1ull << i),c += (1ull << i);
}
}
return ans;
}
int main() {
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++i) op[i] = read(), a[i] = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
for(int i = 1; i <= m; ++i) {
int Q = read();
int x = read(), y = read();
unsigned long long z;
scanf("%llu",&z);
if(Q == 1) {
printf("%llu\n", query(x, y, z));
} else ins(1, id[x], y, z);
}
return 0;
}

时间复杂度约是O(nlog3n)O(nlog^3n)级别的,会TLE。
f[0,1]f[0,1]表示1k1\to k位初始值分别为0,10,1时候的值,就是压位。
合并操作是

1
2
3
4
5
6
7
8
T mov(T &s, T &t) {
T tmp;
tmp.s[0] = ((s.s[0] & t.s[1]) | (~s.s[0] & t.s[0]));
tmp.s[1] = ((s.s[1] & t.s[1]) | (~s.s[1] & t.s[0]));
tmp.t[0] = ((~t.t[0] & s.t[0]) | (t.t[0] & s.t[1]));
tmp.t[1] = ((~t.t[1] & s.t[0]) | (t.t[1] & s.t[1]));
return tmp;
}

比如fL,0f_{L,0},初始值为00,如果输出是11,那么如果想要[L,R][L,R]输出11,就要经过fR,1f_{R,1}
如果输出是00就要经过fR,0f_{R,0}
那么初始值为00,[L,R]的状态就是(fL,0fR,1)(¬fL,0fR,0)(f_{L,0}\land f_{R,1})\lor (\neg f_{L,0}\land f_{R,0})
其他同理。

std

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 110000;
int n, m, k;
unsigned long long MM;
struct Edge {
int u, v, nxt;
}e[N * 2];
struct T {
unsigned long long s[2];
unsigned long long t[2];
void init() {
t[0] = s[0] = 0;
t[1] = s[1] = MM;
}
}t[N * 4];
int head[N], en;
T mov(T &s, T &t) {
T tmp;
tmp.s[0] = ((s.s[0] & t.s[1]) | (~s.s[0] & t.s[0]));
tmp.s[1] = ((s.s[1] & t.s[1]) | (~s.s[1] & t.s[0]));
tmp.t[0] = ((~t.t[0] & s.t[0]) | (t.t[0] & s.t[1]));
tmp.t[1] = ((~t.t[1] & s.t[0]) | (t.t[1] & s.t[1]));
return tmp;
}
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
}
int son[N], siz[N], fa[N], d[N];
void dfs1(int x, int F) {
siz[x] = 1;
fa[x] = F;
d[x] = d[F] + 1;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs1(y, x);
siz[x] += siz[y];
if(siz[son[x]] < siz[y]) son[x] = y;
}
}
int top[N], num, id[N];
unsigned long long a[N], op[N];
unsigned long long b[N], opt[N];
void dfs2(int x, int F) {
id[x] = ++num;
b[id[x]] = a[x];
opt[id[x]] = op[x];
top[x] = F;
if(!son[x]) return;
dfs2(son[x], F);
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].v;
if(y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int ls[N * 4], rs[N * 4];
#define lch (o<<1)
#define rch (o<<1|1)
unsigned long long cal(unsigned long long v, int op, unsigned long long x) {
if(op == 1) return v & x;
if(op == 2) return v | x;
return v ^ x;
}
void up(int o) {
t[o] = mov(t[lch], t[rch]);
}
void build(int o, int l, int r) {
ls[o] = l, rs[o] = r;
if(l == r) {
t[o].s[0] = t[o].t[0] = cal(b[l], opt[l], 0);
t[o].s[1] = t[o].t[1] = cal(b[l], opt[l], MM);
return ;
}
int mid = (l +r) >>1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
up(o);
}
void ins(int o, int x, int op, unsigned long long val) {
if(ls[o] == rs[o]) {
t[o].s[0] = t[o].t[0] = cal(val, op, 0);
t[o].s[1] = t[o].t[1] = cal(val, op, MM);
return;
}
int mid = (ls[o] + rs[o]) >> 1;
if(x <= mid) ins(lch, x, op, val);
else ins(rch, x, op, val);
up(o);
}
void S(T x) {
bitset<64>yy;
yy = x.t[0];
cout<<yy<<endl;
yy = x.t[1];
cout<<yy<<endl;
puts("ASS");
}
T ask(int o, int l, int r) {
if(l <= ls[o] && r >= rs[o])
return t[o];
int mid = (ls[o] + rs[o]) >> 1;
if(r <= mid) return ask(lch, l, r);
if(l > mid) return ask(rch, l, r);
T lt = ask(lch, l, r);
T rt = ask(rch, l, r);
return mov(lt, rt);
}
unsigned long long query(int x, int y, unsigned long long z) {
bool cj = 0;
T t1, t2, res, tmp;
t1.init();
t2.init();
res.init();
while(top[x] != top[y]) {

if(d[top[x]] < d[top[y]]) swap(x, y), swap(t1, t2), cj ^= 1;
tmp = ask(1, id[top[x]], id[x]);
t1 = mov(tmp, t1);
x = fa[top[x]];
}
if(d[x] > d[y]) swap(t1, t2), swap(x, y), cj ^= 1;
tmp = ask(1, id[x], id[y]);
t2 = mov(tmp, t2);
if(cj) swap(t1, t2);
res.s[0] = ((t1.t[0] & t2.s[1]) | (~t1.t[0] & t2.s[0]));
res.s[1] = ((t1.t[1] & t2.s[1]) | (~t1.t[1] & t2.s[0]));
unsigned long long ans = 0;
unsigned long long c = 0;
for(int i = 63; ~i; --i) {
if((res.s[0] >> i) & 1) {
ans ^= (1ull << i);
} else if((c + (1ull << i)) <= z && ((res.s[1] >> i) & 1)) {
ans ^= (1ull << i),c += (1ull << i);
}
}
return ans;
}
int main() {
freopen("4811.in","r",stdin);
freopen("4811.out","w",stdout);
for(int i = 63; ~i; --i)
MM += (1ull<<i);
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++i) op[i] = read(), a[i] = read();
for(int i = 1; i < n; ++i) {
int x = read(), y = read();
addedge(x, y);
addedge(y, x);
}
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
for(int i = 1; i <= m; ++i) {
int Q = read();
int x = read(), y = read();
unsigned long long z;
scanf("%llu",&z);
if(Q == 1) {
printf("%llu\n", query(x, y, z));
} else ins(1, id[x], y, z);
}
return 0;
}