Luogu P3292

- 1 min read

背景

学长讲线性基时挂了几道题，这道题原本写不出来，看了题解后瞎写了一下，又对着原代码调了调，竟然过了。 image.png

打算算一下时间复杂度，分析解法和代码的实现细节。

题意

给一棵树，每个节点i上有一个数字$G_{i}$，q个询问，寻找x-y简单路径上数字的最大异或值。

$M=log(G_{i}) \leq 60$

分析

由最大异或值可以想到线性基，其中插入、求异或最大值的操作都需log(x)复杂度。

x-y简单路径让我想到倍增LCA

void insert(int *a,int x)
{
    for(int i=M;i>=0;--i)
    {
        if((x >> i)&1)
        {
            if(!a[i])
            {
                a[i]=x;
                break;
            }
            else    x^=a[i];
        }
    }
}

int querymax()
{
    int ret=0;
    for(int i=M;i>=0;--i)
    {
        ret=max(ret*1,ret^ans[i]);
    }
    return ret;
}

对q个询问，用倍增预处理。

简单定义线性基的merge操作，$O(M^{2})$

void merge(int *a,int *b)//a <-b
{
    for(int i=0;i<=M;++i)
    {
        if(b[i])
        {
            insert(a,b[i]);
        }
    }
}

线性基的倍增

用三维数组p表示线性基，p[i][j]包含i到f[i][j]的线性基（左闭右开）。

对深度为x的结点i，p[i][j]仅在(0 <=j <= log(x))的范围内有意义。

insert(p[i][0],a[i]);//数据读入时

for(int i=1;(1 << i)<=dep[now];++i)//倍增中
{
	f[now][i]=f[f[now][i-1]][i-1];
	memcpy(p[now][i],p[now][i-1],sizeof(p[now][i-1]));
	merge(p[now][i],p[f[now][i-1]][i-1]);//将后一个插入前一个
}

暴改LCA

在原求LCA的代码上适当修改，在倍增途中合并线性基。

function <int (int,int)> lca=[&](int x,int y)
{
	if(dep[x]>dep[y])   swap(x,y);
	int k=dep[y]-dep[x];
	
	for(int i=19;i>=0;--i)
	{
		if(dep[y]-(1 << i)>=dep[x])
        {
			merge(ans,p[y][i]);
			y=f[y][i];
		}
	}

	if(x==y)
	{
		merge(ans,p[x][0]);//最后一点
		return x;
	}    

	for(int i=19;i>=0;--i)
	{
		if(f[x][i]==f[y][i])    continue;
		merge(ans,p[x][i]);
		merge(ans,p[y][i]);
		x=f[x][i],y=f[y][i];
	}

	merge(ans,p[x][0]);//最后的x,y两点与LCA
	merge(ans,p[y][0]);
	merge(ans,p[f[y][0]][0]);//保证p不超定义域

	return f[x][0];

};