首页 > 代码库 > P2001xor-sigma 字典树，然而好坑
P2001xor-sigma 字典树，然而好坑
https://vijos.org/p/2001
设perXor[i]表示1---i的前缀异或值。
那么要得到某一段的异或值，只需要perXor[j] ^ perXor[i - 1]
那么我们把perXor[n]先加入去字典树，然后用perXor[n - 1]去找，找到的就是下标n的贡献。
同理，然后把perXor[n - 1]插进去，用perXor[n - 2]找，就会是下标n - 1的贡献。因为这个时候它可以是
perXor[n - 2] ^ perXor[n - 1]（因为perXor[n - 1]已经在字典树了，）那么这个时候对应的就是a[n - 1] 自己了。
同理它可以是perXor[n - 2] ^ perXor[n]，就是a[n - 1] ^ a[n]了。
当然，它还有个m的限制，这个可以加个删除操作即可。
需要注意的是：
1、unsigned int并不是保留低31位，它是对2^32取模，而2^32有33位。
2、字典树的大小要开好，字典树的struct node *pNext[]只需2个即可。因为状态只有0或1
3、判断第i位是否是1或者0，是((1 << i) & val) >= 1 不要忘记判断，不然re
4、cin、cout请取消同步，卡了我TLE
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 5e5 + 20; int a[maxn]; int perXor[maxn]; struct node { int cnt; struct node * pNext[2]; }tree[maxn * 40]; int t; struct node * create() { struct node *p = &tree[t++]; // p->cnt = 0; // for (int i = 0; i <= 9; ++i) { // p->pNext[i] = NULL; // } return p; } void toInsert(struct node **T, int val) { struct node *p = *T; if (p == NULL) { p = *T = create(); } for (int i = 30; i >= 0; --i) { int id = ((1 << i) & val) >= 1; if (p->pNext[id] == NULL) { p->pNext[id] = create(); } p = p->pNext[id]; p->cnt++; } } void toDel(struct node **T, int val) { struct node *p = *T; if (p == NULL) return; for (int i = 30; i >= 0; --i) { int id = ((1 << i) & val) >= 1; p = p->pNext[id]; p->cnt--; } } int toFind(struct node *T, int val) { struct node *p = T; if (p == NULL) return 0; int ans = 0; // cout << val << endl; for (int i = 30; i >= 0; --i) { int id = ((1 << i) & val) >= 1; if (p->pNext[!id] && p->pNext[!id]->cnt >= 1) { ans |= (1 << i); p = p->pNext[!id]; } else { p = p->pNext[id]; } } return ans; } int listToAdd[maxn]; const LL MOD = (1LL << 31); void work() { int n, m; cin >> n >> m; for (int i = 1; i <= n; ++i) { cin >> a[i]; } for (int i = 1; i <= n; ++i) { perXor[i] = perXor[i - 1] ^ a[i]; } // for (int i = 1; i <= n; ++i) { // cout << perXor[i] << " " ; // } // cout << endl; // unsigned int t = (1LL << 32); // cout << t << endl; long long int ans = 0; struct node *T = NULL; toInsert(&T, perXor[n]); int len = 0; listToAdd[++len] = perXor[n]; int cur = 1; // cout << toFind(T, perXor[n]) << endl; for (int i = n - 1; i >= 0; --i) { ans += toFind(T, perXor[i]); if (ans >= MOD) ans %= MOD; // cout << toFind(T, perXor[i]) << endl; toInsert(&T, perXor[i]); listToAdd[++len] = perXor[i]; if (len - cur + 1 > m) { toDel(&T, listToAdd[cur++]); } } // cout << endl; cout << ans << endl; } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif IOS; work(); return 0; }
P2001xor-sigma 字典树，然而好坑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。