题目传送门:最大异或和 - Problem - Daimayuan Online Judge
分析
不难发现用可以先预处理出异或前缀和,然后一段区间[l, r]的异或和可以用prefix[r] ^ prefix[l - 1]来表示。
现在问题就转化为对于一个r,在[1, r]的区间内找到一个l(当l == r说明区间内只有一个点),使得prefix[r]^prefix[l - 1]最大,那么l - 1的取值范围就是[0, r - 1]。
现在建立一颗trie树,一边插入一边查询,因为数据范围是(2^30)-1,所以我们可以建一颗30层的树,从上往下表示从第30位到第0位,然后将数字插入到树中,每个点有一个标记,表示是prefix中的下标,另外还有两个指针指向0儿子和1儿子。经过的边表示这个数字的值。
那么现在我们贪心地想,假如现在prefix[r] = x,那么我们找一个y,从高位到低位,尽量地使得y的高位的x的高位不同,可以使得异或结果尽可能大,如果没办法不同,那就只能相同咯。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 9; struct Node { int id, son[2]; }t[maxn * 31]; int N, a[maxn], prefix[maxn], tidx = 1;//1 is the root of tree void insert(int x, int id) { for(int i = 30, o = 1;i >= 0; -- i) { int k = x >> i & 1;//k is the val of x[i] if(!t[o].son[k])t[o].son[k] = ++ tidx; o = t[o].son[k]; if(i == 0)t[o].id = id; } } int findMaxId(int x)//返回l - 1 { int res = 0; for(int i = 30, o = 1;i >= 0; -- i) { int k = x >> i & 1; if(t[o].son[k ^ 1])o = t[o].son[k ^ 1]; else o = t[o].son[k]; if(i == 0)res = t[o].id; } return res + 1; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> N; for(int i = 1;i <= N; ++ i)cin >> a[i]; for(int i = 1;i <= N; ++ i)prefix[i] = prefix[i - 1] ^ a[i]; insert(0, 0); for(int i = 1;i <= N; ++ i) { int l = findMaxId(prefix[i]); cout << (prefix[i] ^ prefix[l - 1]) << ' ' << l << '\n'; insert(prefix[i], i); } return 0; }
Comments NOTHING