E. Beautiful Subarrays

思路

顯然有$a_i?a_{i+1}?\dots \dots ?a_n=(a_1?a_2?\dots \dots ?a_n)?(a_1?a_2?\dots \dots ?a_{i?1})$

所以我們可以先求一遍異或前綴和，然后再通過枚舉右端點，去查找有多少個左端點符合要求。

假設我們當前枚舉到$i$這個位置，前$i$個數的異或前綴和是$a$，我們要查找異或值大于等于$k$的，顯然我們可以去找一個$x$，滿足$a?k=x$，這個時候大于等于$x$的數就是滿足要求的數了，這個操作我們也可以通過一顆$01trie$樹來進行查找。

分四種情況:

• a 的當前位二進制數是0，k的當前位二進制數也是0，如果我們選擇一個數的當前位是1，顯然與a異或之后會變大，所以對答案有貢獻，所以我們加上答案，然后到當前位上是0的地方去繼續尋找。
• a的當前位二進制數是0， k的當前位二進制數是1，顯然我們要使查找值不變小，一定要到當前位是1上去找，這個時候對答案沒有哦貢獻。
• a的當前位二進制數是1， k的當前位二進制數是0，如果我們選擇1，異或結果變大，對答案有貢獻，所以加上答案，走到當前位是1的地方去繼續尋找答案。
• a的當前位二進制數是1， k的當前位二進制也是1，這個時候要保證異或結果不變小，只能到當前位是0的地方去尋找。

最后再特判一下剛好相等的情況就OK了。

代碼

/*Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h>#define mp make_pair #define pb push_back #define endl '\n' #define mid (l + r >> 1) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define ls rt << 1 #define rs rt << 1 | 1using namespace std;typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii;const double pi = acos(-1.0); const double eps = 1e-7; const int inf = 0x3f3f3f3f;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 4e7 + 10;int trie[N][2], tot, num[N];void insert(int x) {int rt = 0;for(int i = 30; i >= 0; i--) {int now = x >> i & 1;if(!trie[rt][now]) trie[rt][now] = ++tot;rt = trie[rt][now];num[rt]++;} }int find(int a, int b) {int ans = 0, rt = 0;for(int i = 30; i >= 0; i--) {int u = a >> i & 1, v = b >> i & 1;if(!u) {if(v) {if(!trie[rt][1]) return ans;rt = trie[rt][1];}else {ans += num[trie[rt][1]];if(!trie[rt][0]) return ans;rt = trie[rt][0];}}else {if(!v) {ans += num[trie[rt][0]];if(!trie[rt][1]) return ans;rt = trie[rt][1];}else {if(!trie[rt][0]) return ans;rt = trie[rt][0];}}}return ans + num[rt]; }const int N1 = 1e6 + 10;int a[N1], n, k;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);ll ans = 0;n = read(), k = read();for(int i = 1; i <= n; i++) {a[i] = read();a[i] ^= a[i - 1];}insert(0);//插入0，有可能這個數自己就比k大。for(int i = 1; i <= n; i++) {ans += find(a[i], k);insert(a[i]);}printf("%lld\n", ans);return 0; }

總結

以上是生活随笔為你收集整理的E. Beautiful Subarrays（思维 01 trie 树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。