字典树，AcWing 5726. 连续子序列

本文主要是介绍字典树，AcWing 5726. 连续子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

5726. 连续子序列 - AcWing题库

---

二、解题报告

1、思路分析

字典树存储前缀和

考虑边遍历计算前缀和，边查询字典树

查询流程：

记当前前缀和为s

如果当前位k为1，那么s 必须 走当前位和自己不同的结点

如果当前位k为0，那么我们加上当前位和s不同的结点记录的前缀数目，然后走当前位和s相同的结点

---

卡常有点难受x_x，动态开3e7跑出来6000ms+会卡掉，静态开3e7是3800ms

2、复杂度

时间复杂度： O(nlogn)空间复杂度：O(30N)，试出来的

3、代码详解

​

#include <bits/stdc++.h>using namespace std;typedef long long LL;constexpr int N = 1000010, M = 3e7 + 10;int n, k;
int a[N], s[N];
int tr[M][2], idx;
int cnt[M];void insert(int x)
{int p = 0;for (int i = 29; i >= 0; i -- ){int u = x >> i & 1;if (!tr[p][u]) tr[p][u] = ++ idx;p = tr[p][u];cnt[p] ++ ;}
}int query(int x)
{int res = 0, p = 0;for (int i = 29; i >= 0; i -- ){int u = x >> i & 1, v = k >> i & 1;if (v == 0){res += cnt[tr[p][u ^ 1]];if (!tr[p][u]) return res;p = tr[p][u];}else{if (!tr[p][u ^ 1]) return res;p = tr[p][u ^ 1];}}res += cnt[p];return res;
}void solve()
{cin >> n >> k;for (int i = 1; i <= n; i ++ ) cin >> a[i];for (int i = 1; i <= n; i ++ )s[i] = s[i - 1] ^ a[i];insert(s[0]);LL res = 0;for (int i = 1; i <= n; i ++ ){res += query(s[i]);insert(s[i]);}cout << res << "\n";
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;while (T -- ) solve();return 0;
}

这篇关于字典树，AcWing 5726. 连续子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---