nowcoder多校4-xor(线段树维护线性基)

题目链接:nowcoder多校4-xor

题意:

给定n个集合,每个集合里有若干个数,然后给出m个询问,每次询问一个区间[l,r],询问区间内的每个集合是否都可以通过异或表出x。

题解:

线段树维护线性基,然后合并时做线性基的交运算,查询给定区间的线性基的交是否可以表出x即可。

参考代码:

#include <bits/stdc++.h>
#define IL inline
using namespace std;
typedef long long ll;
typedef double db;
const int MAXN = 5e4 + 5;
struct Linear_basis
{

    ll a[32], b[32];
    int cnt;
    Linear_basis() //初始化
    {
        cnt = 0;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
    }
    void insert(ll val) //插入新元素
    {
        for (int i = 31; i >= 0; i--)
            if (val & (1ll << i))
            {
                if (!a[i])
                {
                    a[i] = val;
                    break;
                }
                else
                    val ^= a[i];
            }
    }
    int query_max(int x = 0) //查询最大异或和
    {
        int ret = x;

        for (int i = 31; i >= 0; i--)

            if ((ret ^ a[i]) > ret)
                ret ^= a[i];

        return ret;
    }
    int query_min(int x = 0) //查询最小异或和
    {
        int ret = x;
        for (int i = 0; i <= 31; i++)
            if (ret > (a[i] ^ ret))
                ret ^= a[i];
        return ret;
    }
    void rebuild()
    {
        for (int i = 31; 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 <= 30; i++)
            if (a[i])
                b[cnt++] = a[i];
    }
    int query_kth_min(int k) //对线性基重置之后就可以查询第k小异或和
    {
        int ret = 0;
        if (k >= (1LL << cnt))
            return -1;
        for (int i = 31; i >= 0; i--)
            if (k & (1LL << i))
                ret ^= a[i];
        return ret;
    }
    bool query_exist(ll x) //查询x是否可以由该线性基线性表出
    {
        for (int i = 31; i >= 0; i--)
            if (x & (1ll << i))
                x ^= a[i];
        return (x == 0);
    }
    Linear_basis merge_and(Linear_basis m) //合并线性基  和运算
    {
        Linear_basis 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] & (1ll << j))
                {
                    if (ret.a[j])
                        m.a[i] ^= ret.a[j];
                    else
                    {
                        ret.a[j] = m.a[i];
                        break;
                    }
                }
        return ret;
    }
    Linear_basis merge_or(Linear_basis x, Linear_basis y) //合并线性基  与运算
    {
        Linear_basis temp = x, ret, d;
        for (int i = 31; i >= 0; i--)
            d.a[i] = 1ll << i;
        for (int i = 31; i >= 0; i--)
            if (y.a[i])
            {
                ll v = y.a[i], k = 0;
                bool flag = 1;
                for (int j = 31; j >= 0; j--)
                    if (v & (1ll << j))
                    {
                        if (temp.a[j])
                        {
                            v ^= temp.a[j];
                            k ^= d.a[j];
                        }
                        else
                        {
                            flag = 0;
                            temp.a[j] = v;
                            d.a[j] = k;
                            break;
                        }
                    }

                if (flag)
                {
                    ll v = 0;
                    for (int j = 31; j >= 0; j--)
                    {
                        if (k & (1ll << j))
                            v ^= x.a[j];
                    }
                    ret.insert(v);
                }
            }
        return ret;
    }
} sum[MAXN << 2], aa[MAXN];
int n, m;
void pushup(int rt)
{
    sum[rt] = sum[rt].merge_or(sum[rt << 1], sum[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
    if (l == r)
    {
        sum[rt] = aa[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
bool query(int L, int R, ll x, int l, int r, int rt)
{
    if (L <= l && r <= R)
        return sum[rt].query_exist(x);
    int mid = (l + r) / 2;
    bool res = 1;
    if (L <= mid)
        res &= query(L, R, x, l, mid, rt << 1);
    if (R > mid)
        res &= query(L, R, x, mid + 1, r, rt << 1 | 1);
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int num;
        scanf("%d", &num);
        for (int j = 1; j <= num; j++)
        {
            ll x;
            scanf("%lld", &x);
            aa[i].insert(x);
        }
    }
    build(1, n, 1);
    while (m--)
    {
        int l, r;
        ll x;
        scanf("%d%d%lld", &l, &r, &x);
        if (query(l, r, x, 1, n, 1))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

发表留言

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