线性基

扯点线性基

本博客代码未经过测试

线性基是一个能够在每次时间复杂度(O(log_2d)),d是数字的位数内处理异或最大最小的数据结构。

问题：请你维护一个数据结构，支持插入一个数，求这些数任意异或得到的结果是否可能为某一个数、最大值、最小值、第k小值。

做法：开一个数组a[MAXN],MAXN是数字最高位数。

a[i]表示当前线性基内任意异或出来的数字中，最高位为i的任意一个数字。

#define MAXN 60
long long a[64];

插入x|判断x是否存在

从高位到低位枚举所有位数，如果x的第i位有值：如果a[i]不存在，则a[i]=x，并退出。如果a[i]存在，令x^=a[i]。如果最后x变成了0，那么说明x在线性基内。

bool insert(long long x)
{
    for(int i = MAXN; i >= 0; i--)
    {
        if(x & (1LL << i))
        {
            if(a[i] == 0)
            {
                a[i] = x;
                break;
            }
            x ^= a[i];
        }
    }
    return x > 0;
}

查询最大值

从高位到低位扫描线性基。如果异或之后答案变大，就把这一位异或到答案。

long long getmax()
{
    long long ans = 0;
    for(int i = MAXN; i >= 0; i--)
    {
        if((ans ^ a[i]) > ans)
            ans ^= a[i];
    }
    return ans;
}

查询最小值

从低位到高位扫描线性基。最低位上的线性基即为答案。

long long getmin()
{
    for(int i = 0; i <= MAXN; i++)
    {
        if(a[i] > 0)
            return a[i];
    }
}

第k小

首先我们要改造一下线性基。我们把线性基改造成每一位相互独立，意思就是对于第i位，线性基上只有一个未知的第i位可能是1。具体如何改造，就是从高位向低位扫描，对于第i位线性基a[i]，对于j<i，如果a[i]的第j位是1，就让a[j]异或上a[i]。

查询的时候，将k进行二进制拆分，对于的1位，就异或对应的线性基。

最终得到的答案是第k小值。

int p[64],cnt;
void rebuild()
{
	for(int i = MAXN; i >= 0; i--)
    {
        for(int j = i - 1; j >= 0; j--)
            if(a[i] & (1LL << j))
                a[i] ^= a[j];
    }
    for(int i = 0; i <= MAXN; i++)
    {
        if(a[i])
            p[cnt++]=d[i];
    }
}

long long query(long long k)
{
    long long ans=0;
    rebuild();
    if(k >= (1LL << cnt))
    	return -1;
    for(int i = MAXN; i >= 0; i--)
    {
        if(k & (1LL << i))
            ans ^= p[i];
    }
    return ans;
}