精品文档---下载后可任意编辑零和自由序列的子序列和问题的开题报告题目零和自由序列的子序列和问题问题描述给定一个长度为 n 的序列 a，其元素为正整数和负整数。若对于任意长度大于 1 的子序列，其元素之和不为 0，则称该序列为零和自由序列。现有多个询问，每次询问给出一个区间[l,r]，求区间[l,r]中所有零和自由子序列的元素之和。数据范围1≤n≤2×10^5，1≤q≤2×10^5，-10^9≤a[i]≤10^9。分析一开始看到此题，我考虑用 dp 来解决。设 dp[i][j]为第 i 位到第 j 位的零和自由子序列的和，那么我们的目标就是要求 dp[l][r]的值，显然区间 dp 不是一个可行的算法，因为它的时间复杂度是 n 的 4 次方，所以需要对其优化。考虑用前缀和进行优化，设 s[i]为前 i 个数之和，则 dp[i][j]可以转化为(1≤u≤i, j≤v≤n) ∑ (s[u]-s[i-1]) - (s[u]-s[j]) != 0，化简后为 s[i-1]-s[j]-s[s]-s[v-1]!=0，即(s[i-1]-s[j]) != (s[s]-s[v-1])，在固定 i、j的情况下，可以把每个 s[k]看做一个点，那么问题就变成了求不同的（s[i-1]-s[j])的数量，前者可以直接用前缀和优化，后者可以用哈希表解决。但是这个哈希表的 key 可能非常大，直接将其存储在数组内会爆掉，所以考虑对哈希值进行离散化，具体做法是将哈希值和其对应的元素值作为结构体存储在一个 vector 中，并对 vector 进行排序。这样就能用vector 的下标作为离散化后的值了。参考代码
