题目大意
有一个长度为$n$的序列，支持两种操作：
$0\,x\,y$：把$x$位置上的数换成$y$。
$1\,x\,y$：在$[x,y]$中，请你任选一些数使他们的异或和最大。
题目分析
不妨用线段树维护线性基，每次单点修改时暴力重构线性基，询问时合并线性基。
因为线性基最多$63$个，因此时间复杂度是$O(n\log n63^2)$。
代码
此题重载运算符略微卡常。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
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=30005,MAX_BASE=63;
struct Linear_Bases {
LL b[MAX_BASE+5];
Linear_Bases() {
fill(b,b+MAX_BASE+1,0);
}
Linear_Bases operator + (LL num) {
Linear_Bases a=*this;
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(a.b[j]) { //该位存在基
num^=a.b[j];
continue;
}
a.b[j]=num;
for(int k=j-1; k>=0; k--)if(a.b[j]>>k&1)a.b[j]^=a.b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(a.b[k]>>j&1)a.b[k]^=a.b[j];
break;
}
return a;
}
void operator += (const LL num) {
*this=*this+num;
}
Linear_Bases operator + (const Linear_Bases& b) {
Linear_Bases a=*this;
for(int i=0; i<=MAX_BASE; i++)
if(b.b[i])a+=b.b[i];
return a;
}
void operator += (const Linear_Bases b) {
*this=*this+b;
}
LL cal() { //最大异或和
LL ans=0;
for(int i=0; i<=MAX_BASE; i++)ans^=b[i];
return ans;
}
};
struct Segment_Tree {
struct Tree {
int left,right;
Linear_Bases lb;
Tree(int l=0,int r=0):left(l),right(r),lb(Linear_Bases()) {}
} tree[maxn<<2];
void build(int index,int Left,int Right,LL* a) {
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].lb+=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=tree[ls].lb+tree[rs].lb;
}
void modify(int index,int target,LL v) {
if(tree[index].left>target||tree[index].right<target)return;
if(tree[index].left==tree[index].right) {
tree[index].lb=Linear_Bases()+v;
return;
}
modify(ls,target,v);
modify(rs,target,v);
push_up(index);
}
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 query(ls,Left,Right)+query(rs,Left,Right);
}
} st;
int n,q;
LL a[maxn];
int main() {
n=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
st.build(1,1,n,a);
while(q--) {
int opt=Get_Int(),x=Get_Int();
LL y=Get_Int();
if(opt==0)st.modify(1,x,y);
else {
Linear_Bases lb=st.query(1,x,y);
printf("%lld\n",lb.cal());
}
}
return 0;
}
