「HDU-6579」Operation (线性基)

发表于 | 分类于 ，

「HDU-6579」Operation
贪心+线性基，在LR区间内取任意个元素，求最大异或和

题意

给定一个长度为n的序列，有如下两种操作：

  1. 求L,R区间内任意个元素的最大异或和；
  2. 在序列末尾插入一个元素；

本题强制在线。

题解

考虑对每个点维护一个线性基，插入操作为继承上一个点的线性基并插入当前点的值。

维护每个基底组成的点g[i]，考虑贪心，尽可能使组成线性基的点更靠近R。

对于某一位的点g[i]，如果pos>g[i]，则把pos与g[i]交换，使pos成为线性基的基底。

对于每个询问，查询第R个线性基所有pos大于L的基底能组成的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

int n;
inline int getpos(int x, int lasans) { return (x ^ lasans) % n + 1; }

struct LinearBasis
{
    int f[30], g[30];

    void ins(int x, int pos)
    {
        for(int i = 29; ~i; i --)
        {
            if((x >> i) & 1)
            {
                if(f[i])
                {
                    if(g[i] <= pos) { x ^= f[i]; f[i] ^= x; swap(g[i], pos); }
                    else x ^= f[i];
                }
                else { f[i] = x; g[i] = pos; break; }
            }
        }
    }

    int query(int l)
    {
        int res = 0;
        for(int i = 29; ~i; i --) if(g[i] >= l) res = max(res, res ^ f[i]);
        return res;
    }
}base[maxn];

int main()
{
    int t, q, op, l, r, x;
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &x);
            base[i] = base[i - 1];
            base[i].ins(x, i);
        }
        int ans = 0;
        while(q --)
        {
            scanf("%d", &op);
            if(op == 0)
            {
                scanf("%d%d", &l, &r);
                l = getpos(l, ans), r = getpos(r, ans);
                if(l > r) swap(l, r);
                printf("%d\n", ans = base[r].query(l));
            }
            else
            {
                scanf("%d", &x); n ++;
                base[n] = base[n - 1], base[n].ins(x ^ ans, n);
            }
        }
    }
    return 0;
}