P3292 [SCOI2016]幸运数字
这题用LCT是可做的。
至少我卡过去了
维护路径上的线性基，合并即可。每次查询线性基内最大值。
时间复杂度为三只log。
代码（吸氧最慢的点跑了3.89秒）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 20010
#define ll long long
#define __int520 signed
#define LEN 1<<21
char buf[LEN],*SS,*TT;
char gtc(){
if(SS==TT){
TT=(SS=buf)+fread(buf,1,LEN,stdin);
if(SS==TT) return EOF;
}
return *SS++;
//return getchar();
}
int rd(){
char c=gtc();
int ans=0;
while(c<'0'||c>'9')c=gtc();
while(c>='0'&&c<='9'){ans=(ans<<3)+(ans<<1)+(c^48);c=gtc();}
return ans;
}
ll rdll(){
char c=gtc();
ll ans=0;
while(c<'0'||c>'9')c=gtc();
while(c>='0'&&c<='9'){ans=(ans<<3)+(ans<<1)+(c^48);c=gtc();}
return ans;
}
#undef LEN
int sta[63];
inline void write(ll x) {
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) putchar(sta[--top] + 48);
putchar('\n');
}
struct xxj{
ll p[61];
void ins(ll w,int mx=60){
for(int i=mx;i>=0;i--){
if(w>>i){
if(!p[i]){
p[i]=w;
break;
}
w^=p[i];
}
}
}
ll getmx(){
ll re=0;
for(int i=60;i>=0;i--){
if((re^p[i])>re){
re^=p[i];
}
}
return re;
}
void clear(){
memset(p,0,sizeof p);
}
xxj(){
memset(p,0,sizeof p);
}
};
xxj merge(const xxj &a,const xxj &b){
xxj re=a;
for(int i=60;i>=0;i--){
if(b.p[i])re.ins(b.p[i],i);
}
return re;
}
struct chr{
int tag;
chr *f;
chr *son[2];
ll num;
xxj ans;
}tree[maxn];
chr *stack[maxn];
void push_tag(chr *x){
x->tag^=1;
swap(x->son[0],x->son[1]);
}
void pushup(chr *x){
if(x->son[0]&&x->son[1])x->ans=merge(x->son[0]->ans,x->son[1]->ans);
else if(!(x->son[0]||x->son[1]))x->ans.clear();
else x->ans=x->son[0]?x->son[0]->ans:x->son[1]->ans;
x->ans.ins(x->num);
}
void pushdown(chr *x){
if(!x)return;
if(x->tag){
if(x->son[0])push_tag(x->son[0]);
if(x->son[1])push_tag(x->son[1]);
x->tag^=1;
}
}
bool nroot(chr *x){
if(!x->f)return 0;
return x->f->son[0]==x||x->f->son[1]==x;
}
void rot(chr *x){
chr *y=x->f;
chr *z=y->f;
int t1=y->son[1]==x;
int t2;
if(z)t2=z->son[1]==y;
int t3=nroot(y);
y->son[t1]=x->son[t1^1];
if(x->son[t1^1])
x->son[t1^1]->f=y;
x->son[t1^1]=y;
y->f=x;
x->f=z;
if(z&&t3)z->son[t2]=x;
pushup(y);
}
void splay(chr *x){
int pos=0;
chr* t=x;
stack[pos]=x;
while(nroot(t)){
t=t->f;
pos++;
stack[pos]=t;
}
while(pos>=0){
pushdown(stack[pos]);
pos--;
}
while(nroot(x)){
chr *y=x->f;
if(nroot(y)){
chr *z=y->f;
int t1=y->son[1]==x;
int t2=z->son[1]==y;
if(t1==t2)rot(y);
else rot(x);
}
rot(x);
}
pushup(x);
}
void access(chr *x){
splay(x);
x->son[1]=NULL;
pushup(x);
while(x->f){
splay(x->f);
x->f->son[1]=x;
pushup(x->f);
x=x->f;
}
}
chr* findroot(chr *x){
access(x);
splay(x);
while(x->son[0]){
pushdown(x);
x=x->son[0];
}
splay(x);
return x;
}
void makeroot(chr *x){
access(x);
splay(x);
x->son[1]=NULL;
push_tag(x);
}
void split(chr *x,chr *y){
makeroot(x);
access(y);
splay(y);
}
void link(chr *x,chr *y){
makeroot(x);
if(findroot(y)==x)return;
x->f=y;
}
void cut(chr *x,chr *y){
makeroot(x);
if(findroot(y)==x&&y->f==x&&(!y->son[0])){
x->son[1]=NULL;
y->f=NULL;
pushup(x);
}
}
__int520 main(){
int n=rd();int q=rd();
for(int i=1;i<=n;i++){
tree[i].num=rdll();
pushup(tree+i);
}
for(int i=1;i<=n-1;i++){
int s=rd();int t=rd();
link(tree+s,tree+t);
}
for(int i=1;i<=q;i++){
int s=rd();int t=rd();
split(tree+s,tree+t);
write(tree[t].ans.getmx());
}
return 0;
}