计蒜客A1607-XOR(线段树+线性基)

题目链接:[计蒜客A1607-XOR]][1]

题意:

给定一个长度为n的序列,然后有q个询问,每次询问一个区间[l,r],Z=k|(a[i]^a[j]···),求最大的Z。

题解:

首先对k取反,然后与序列中的数做和运算,然后复原k,就等价于求原区间中与k的最大异或和。

用线段树维护区间线性基,暴力合并即可。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 1e4 + 4;
const int MAXM = 1e4 + 4;
const int inf = 1e4 + 4;
const int mod = 1e4 + 4;
int T, n, q, k;
int a[MAXN];
struct L_B
{
    int a[32];
    void init()
    {
        memset(a, 0, sizeof(a));
    }
    bool insert(int val)
    {
        for (int i = 30; i >= 0; i--)
            if (val & (1 << i))
            {
                if (!a[i])
                {
                    a[i] = val;
                    break;
                }
                else
                    val ^= a[i];
            }
        return val > 0;
    }
    int query_max(int x = 0)
    {
        int ret = x;
        for (int i = 30; i >= 0; i--)
            if ((ret ^ a[i]) > ret)
                ret ^= a[i];
        return ret;
    }
    L_B merge(L_B m)
    {
        L_B ret;
        for (int i = 0; i < 31; i++)
            ret.a[i] = a[i];
        for (int i = 0; i < 31; i++)
            for (int j = i; j >= 0; j--)
                if (m.a[i] & (1 << j))
                {
                    if (ret.a[j])
                        m.a[i] ^= ret.a[j];
                    else
                    {
                        ret.a[j] = m.a[i];
                        break;
                    }
                }
        return ret;
    }
} sum[MAXN << 2];
IL void pushup(int rt)
{
    sum[rt] = sum[rt << 1].merge(sum[rt << 1 | 1]);
}
IL void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt].init();
        sum[rt].insert(a[l]);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
IL L_B query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum[rt];
    int mid = (l + r) >> 1;
    if (L <= mid && mid < R)
        return query(L, R, l, mid, rt << 1).merge(query(L, R, mid + 1, r, rt << 1 | 1));
    if (L <= mid)
        return query(L, R, l, mid, rt << 1);
    if (R > mid)
        return query(L, R, mid + 1, r, rt << 1 | 1);
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d", &n, &q, &k);
        k = ~k;
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]), a[i] &= k;
        k = ~k;
        build(1, n, 1);
        while (q--)
        {
            int l, r;

            scanf("%d%d", &l, &r);
            L_B A = query(l, r, 1, n, 1);
            printf("%d\n", A.query_max(k));
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。