第二周1

利用前缀和对同类数据处理

什么是前缀和？

前缀和是某项数组下标（包括该点）之前的所有元素的和。设a[]为原数组，S[]为前缀和数组，可以得到以下递推式

初学思路

S数组是对a数组预处理的结果，其中保存的是a数组中[i,j]的元素之和，从而实现对区间和的O(1)效率的查找。

进一步

从S数组可以快速求出原数组某段区间和，转化成S数组可以实现对原数组中符合某种限制条件的区间信息的归并处理，根据限制条件的不同我们可以使用一个滑动窗口在S数组中滑动，选定或维护我们所需要的某段集合，实现从枚举点到枚举集合的优化处理，思考方向也从元素到元素集合的转化。

题目：递增三元组

链接：https://www.acwing.com/problem/content/1238/

题面

给定三个整数数组

请你统计有多少个三元组 (i,j,k)(i,j,k) 满足：

输入格式

第一行包含一个整数 N。

第二行包含 N 个整数 A1,A2,…AN。

第三行包含 N 个整数 B1,B2,…BN。

第四行包含 N 个整数 C1,C2,…CN。

输出格式

一个整数表示答案。

数据范围

输入样例

3
1 1 1
2 2 2
3 3 3

输出样例

27

暴力思路

枚举每一种可能性，时间复杂度为O(n^3)，显然会TLE爆掉。

for( int i = 1 ; i <= n ; i++ )
	for( int j = 1 ; j <= n ; j++ )
        if( a[i] < b[j] )
            for( int k = 1 ; k <= n ; k++ )
                if( b[j] < c[k] ) res++;

暴力代码分析

我们可以发现，对于每个确定的Bi,A，C数组中都能找到一个符合条件的集合，而B数组内元素的大小关系又使得目标集合出现重叠部分，在暴力枚举每个元素的时候必然多次无用重复。

前缀和优化

观察条件不等式，可以发现Bi将A数组内元素划分为小于Bi和大于等于Bi两部分，同理C也是。我们可以利用前缀和对A数组进行预处理得到S数组，再根据限制条件，用一个滑动窗口在S数组内移动，得到目标集合内元素出现之和，实现对O(n^2)枚举的优化。

for( int i = 0 ; i < n ; i++ ) scanf("%d",&a[i]),a[i]++;//前缀和下标从1开始，每个元素++
for( int i = 0 ; i < n ; i++ ) cnt[a[i]]++;//桶排序计数
for( int i = 1 ; i < N ; i++ ) s[i] = s[i-1] + cnt[i];//得到前缀和数组
for( int i = 0 ; i < n ; i++ ) a_sum[i] = s[b[i]-1];//a_sum[i]代表A数组内小于Bi-1的集合内元素出现次数之和

K倍区间（严格来讲算是一个小优化技巧）

链接：https://www.acwing.com/problem/content/1232/

题面

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j][i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

解题思路

显然是构建前缀和数组，枚举每段集合，判断条件为S[r] - S[i-1]%k== 0，时间复杂度为O(n^2)，TLE炸开。

暴力代码

for( int i = 1 ; i <= n ; i++ )
        for( int j = i+1 ; j <= n ; j++ )
            if( (b[j]-b[i])%k==0&&(b[j]-b[i])>=k ) sum++;

解题优化

S[r] - S[i-1]%k== 0 ---> S[i-1] % k == S[r] % k

代码

long long res = 0;
for( int i = 1; i <= n ; i++ )
{
	q[i] = q[i-1] + a[i];//前缀和数组构建
        
	res += cnt[ q[i] % k ];//首先得成对出现，后续才能任意匹配，所以第一次先+0
        
	cnt[ q[i] % k] ++;//桶排记录一下出现次数
}  
    cout<<res+cnt[0]<<endl;

附上mod运算学习链接：https://blog.csdn.net/mahoon411/article/details/105637663

第二周1

原文：https://www.cnblogs.com/malfood/p/14533661.html