隐藏
「SCOI2016」幸运数字 - 线性基+倍增 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「SCOI2016」幸运数字 - 线性基+倍增

题目大意

    给出一棵树,求这棵树两点之间路径上点权的异或和最大值。


题目分析

这道题很像的一道题。
我们同样可以使用树链剖分+线段树+线性基的方法做这道题。
因为一段连续的区间要经过树链剖分和线段树两次定位,而线性基合并代价不能视作常数,因此时间效率低下,$O(q\log^2n 60^2)$。
卡常卡出屎了,$80$分未过,如果使用重载只有$60$分,不知道其他人怎么过的。

考虑使用倍增定位区间。
我们用$f[i,j]$表示$i$点到其$2^j$倍祖先的线性基(包含$i$点,不包含$2^j$倍祖先)。
那么我们就可以在$O(q\log n 60^2)$内完成操作。

听说这道题还有$O(q\log n 60)$的点分的方法,我不会,%%%


代码

倍增$100$分。

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=20005,MAX_BASE=60;

struct Linear_Bases {
LL b[MAX_BASE+5];
Linear_Bases() {
fill(b,b+MAX_BASE+1,0);
}
void add(LL num) {
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) { //该位存在基
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
void merge(const Linear_Bases& b) {
for(int i=0; i<=MAX_BASE; i++)
if(b.b[i])add(b.b[i]);
}
LL cal() { //最大异或和
LL ans=0;
for(int i=0; i<=MAX_BASE; i++)ans^=b[i];
return ans;
}
} f[maxn][16];

Linear_Bases merge(Linear_Bases a,const Linear_Bases& b) {
for(int i=0; i<=MAX_BASE; i++)
if(b.b[i])a.add(b.b[i]);
return a;
}

int n,q,p[maxn][16],Depth[maxn];
LL a[maxn],b[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void Dfs(int Now,int fa,int depth) {
Depth[Now]=depth;
p[Now][0]=fa;
for(int i=1; i<=15; i++)
if(~p[Now][i-1]) {
p[Now][i]=p[p[Now][i-1]][i-1];
f[Now][i]=merge(f[Now][i-1],f[p[Now][i-1]][i-1]);
}
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs(Next,Now,depth+1);
}
}

LL LCA(int a,int b) {
if(Depth[a]<Depth[b])swap(a,b);
Linear_Bases lb;
for(int i=15; i>=0; i--)
if(Depth[a]-(1<<i)>=Depth[b]) {
lb.merge(f[a][i]);
a=p[a][i];
}
if(a==b) {
lb.merge(f[a][0]);
return lb.cal();
}
for(int i=15; i>=0; i--)
if(p[a][i]!=p[b][i]) {
lb.merge(merge(f[a][i],f[b][i]));
a=p[a][i];
b=p[b][i];
}
lb.merge(merge(f[a][1],f[b][0])); //!!!
return lb.cal();
}

int main() {
memset(p,-1,sizeof(p));
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)f[i][0].add(Get_Int());
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs(1,-1,1);
while(q--) {
int x=Get_Int(),y=Get_Int();
printf("%lld\n",LCA(x,y));
}
return 0;
}

树剖$80$分

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=20005,MAX_BASE=60;

struct Linear_Bases {
LL b[MAX_BASE+5];
Linear_Bases() {
fill(b,b+MAX_BASE+1,0);
}
void add(LL num) {
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) { //该位存在基
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
void merge(const Linear_Bases& b) {
for(int i=0; i<=MAX_BASE; i++)
if(b.b[i])add(b.b[i]);
}
LL cal() { //最大异或和
LL ans=0;
for(int i=0; i<=MAX_BASE; i++)ans^=b[i];
return ans;
}
};

Linear_Bases merge(Linear_Bases a,const Linear_Bases& b) {
for(int i=0; i<=MAX_BASE; i++)
if(b.b[i])a.add(b.b[i]);
return a;
}

struct Segment_Tree {
struct Tree {
int left,right;
Linear_Bases lb;
Tree(int l=0,int r=0):left(l),right(r) {}
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right,LL* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].lb.add(a[Left]);
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid,a);
build(rs,mid+1,Right,a);
push_up(index);
}
void push_up(int index) {
tree[index].lb=merge(tree[ls].lb,tree[rs].lb);
}
Linear_Bases query(int index,int Left,int Right) {
if(tree[index].left>Right||tree[index].right<Left)return Linear_Bases();
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].lb;
return merge(query(ls,Left,Right),query(rs,Left,Right));
}
} st;

int n,q,step=0,father[maxn],Depth[maxn],Size[maxn],Son[maxn],Top[maxn],Dfn[maxn];
LL a[maxn],b[maxn];
vector<int>edges[maxn];

void AddEdge(int x,int y) {
edges[x].push_back(y);
}

void Dfs1(int Now,int fa,int depth) {
father[Now]=fa;
Depth[Now]=depth;
Size[Now]=1;
for(int Next:edges[Now]) {
if(Next==fa)continue;
Dfs1(Next,Now,depth+1);
Size[Now]+=Size[Next];
if(Size[Next]>Size[Son[Now]])Son[Now]=Next;
}
}

void Dfs2(int Now,int top) {
Top[Now]=top;
Dfn[Now]=++step;
b[step]=a[Now];
if(Son[Now])Dfs2(Son[Now],top);
for(int Next:edges[Now]) {
if(Next==father[Now]||Next==Son[Now])continue;
Dfs2(Next,Next);
}
}

LL Query(int from,int to) {
int t1=Top[from],t2=Top[to];
Linear_Bases lb;
while(t1!=t2) {
if(Depth[t1]<Depth[t2]) {
swap(t1,t2);
swap(from,to);
}
lb.merge(st.query(1,Dfn[t1],Dfn[from]));
from=father[t1];
t1=Top[from];
}
if(Depth[from]>Depth[to])swap(from,to);
lb.merge(st.query(1,Dfn[from],Dfn[to]));
return lb.cal();
}

int main() {
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<n; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
AddEdge(y,x);
}
Dfs1(1,0,1);
Dfs2(1,1);
st.build(1,1,n,b);
while(q--) {
int x=Get_Int(),y=Get_Int();
printf("%lld\n",Query(x,y));
}
return 0;
}

姥爷们赏瓶冰阔落吧~