CF1352E Special Elements

CF1352E Special Elements

题意：给你(a)数列，让你判断其中的每个元素是否能写成数列中几个连续元素之和，并统计个数。

这道题乍一看维护前缀和，枚举端点查找。(O(n^2*t))的复杂度，但是一些特性让它的跑不满，就可以过了。

几个非常有意思的数据范围包括：(1leq nleq 8000,1leq a_i leq n)。

注意到他让你求的并不是任意一个数，而是(a_i)，并且(1leq a_i leq n)，也就是说他让你找的数其实只是在一到八千的范围内。对于枚举的(l)，如果(sum[r]-sum[l-1]>8000)，就不需要接着枚举(r)了。

那么处理前缀和，再开8000个桶分别装每一个数据就可以了

for (int l = 1; l < n; l++) 
{
	for (int r = l + 1; r <= n; r ++) 
    {
		int sum = b[r] - b[l - 1];
		if(sum<=n) vis[sum]++;
		else break;
	}
}