P3292 [SCOI2016]幸运数字

发表于 | 阅读数

树上一条链中挑选出某些数 异或和最大。

显然维护线性基，线段树维护线性基暴力合并过于复杂。

考虑维护每个结点到根的线性基。根据求区间线性基的方法。链上记录基内某个基的最大的深度，然后取$[x,lca(x,y)]$和$[y,lca(x,y)]$，进行取该可以取的元素，合并起来。

1
2
3
if (po > pos[i])
    swap(x, p[i]), swap(po, pos[i]);
 x ^= p[i];

复杂度$O(n\log^2 n +q \log ^2n)$

代码 
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 2e4 + 10;
const int mod = 1e9 + 7;
const int MAXL = 61;
const int lg = 20;

class LinearBase
{
public:
    ll p[MAXL];
    int pos[MAXL];
    void clear()
    {
        memset(p, 0, sizeof(p));
    }

    void insert(ll x, int po)
    {

        for (int i = MAXL - 1; i >= 0; i--)
        {
            if (x & (1ll << i))
            {
                if (!p[i])
                {
                    p[i] = x;
                    pos[i] = po;
                    break;
                }
                if (po > pos[i])
                    swap(x, p[i]), swap(po, pos[i]);
                x ^= p[i];
            }
        }
    }
    ll query_max(ll x = 0)
    {
        ll res = x;
        for (int i = MAXL - 1; i >= 0; i--)
            res = max(res, res ^ p[i]);
        return res;
    }

    ll query_min()
    {
        for (int i = 0; i < MAXL; i++)
            if (p[i])
                return p[i];
        return 0;
    }
    void rebuild()
    {
        for (int i = MAXL - 1; i >= 0; i--)
            for (int j = i - 1; j >= 0; j--)
                if ((p[i] >> j) & 1)
                    p[i] ^= p[j];
    }
    void mergeFrom(const LinearBase &other)
    {
        for (int i = 0; i <= MAXL; i++)
            insert(other.p[i], 0);
    }
    ll query_kth(ll k, int n)
    {
        rebuild();
        vector<ll>
            pp;
        for (int i = 0; i < MAXL; ++i)
            if (p[i])
                pp.push_back(p[i]);
        if (pp.size() != n)
            k--;
        if (k > (1LL << pp.size()) - 1)
            return -1;
        ll ans = 0;
        for (int i = 0; i < pp.size(); ++i)
            if (k & (1LL << i))
            {
                ans ^= pp[i];
            }
        return ans;
    }
} lb[N];

vector<int> g[N];
int n, m;
int f[N][lg];
ll a[N], dep[N];
void dfs(int x, int fa)
{
    f[x][0] = fa;
    dep[x] = dep[fa] + 1;
    for (int i = 1; i < lg; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];

    for (int i = 0; i < MAXL; i++)
        lb[x].p[i] = lb[fa].p[i], lb[x].pos[i] = lb[fa].pos[i];
    lb[x].insert(a[x], dep[x]);
    for (int to : g[x])
    {
        if (to != fa)
            dfs(to, x);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    for (int i = lg - 1; i >= 0; i--)
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];
    if (x == y)
        return x;
    for (int i = lg - 1; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
void solve(int x, int y)
{
    LinearBase cb;
    int lc = lca(x, y);

    for (int i = 0; i < MAXL; i++)
    {
        //cout << lb[x].p[i] << lb[i].pos[x] << endl;
        if (lb[x].pos[i] >= dep[lc])
            cb.p[i] = lb[x].p[i];
        else
            cb.p[i] = 0;
    }
    for (int i = 0; i < MAXL; i++)
    {
        if (lb[y].pos[i] >= dep[lc])
            cb.insert(lb[y].p[i], 0);
    }
    printf("%lld\n", cb.query_max());
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    while (m--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        solve(x, y);
    }
}