wordpress图片远程,河源网站制作1993seo,免费个人电子版简历下载,广州制作网站公司电话一、题目
1、题目描述 2、输入输出
2.1输入 2.2输出 3、原题链接
5726. 连续子序列 - AcWing题库 二、解题报告
1、思路分析
字典树存储前缀和
考虑边遍历计算前缀和#xff0c;边查询字典树
查询流程#xff1a;
记当前前缀和为s
如果当前位k为1#xff0c;那么s …一、题目
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.husing 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;
}
