前缀和
有一个半月没有更新了，可能是因为前段时间琐碎的事情比较多，本文介绍一下前缀和，前缀和是处理数组的一种技巧，用一个数组来存储下标从1到i的和，通常情况下这样可以减少时间复杂度，下面通过列举几道题来感受一下这个方法，下面的题目大多来自于Acwing。
Acwing3723 字符串查询
给你单词S和Q个询问，每次询问时，你会得到整数A、B、C和D。我们令单词X是由S的第A到B个字母组成，单词Y是由S的第C到D个字母组成。你需要回答，是否能够重新排列单词Y中的字母，得到单词X。
输入格式：第一行输入一个单词S，仅由小写字母组成。第二行输入一个正整数Q。接下来的Q行，每行四个整数A，B，C，D。
输出格式：每次询问，如果能，输出DA，否则输出NE。 1<=|S|<=50000。
题目分析：
简单来说，就是看这两个区间内的(a,z)的字符个数是否相同，一个最朴实无华的方法就是把这两个字字符串截下来，然后对其进行排序，最后再挨个比较，当然，不出意外的话会超时。这种情况下的时间复杂度是O((b-a)*log(b-a))，最差情况就是 O(nlog(n)),比这个复杂度小的只有O(n)(明显这道题是不可能有O(1)的)，所以就需要寻找一种方法，在遍历一遍或几遍S后，便可判断出结果。
我们可以预处理一个前缀和数组 sum[i][c]，表示前 i 个字符中，字母 c 出现的次数。这样对于任意区间 [l, r]，字母 c 的出现次数就是 sum[r][c] - sum[l-1][c]。只要两个区间内26个字母的出现次数都相等，就说明可以通过重排得到相同的字符串。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N=50010,M=27;
int s[N][M];
string str;
bool check(int a,int b,int c,int d){
for(int i=0;i<26;i++){
if(s[b][i]-s[a-1][i]!=s[d][i]-s[c-1][i]){
return false;
}
}
return true;
}
int main(){
cin>>str;
for(int i=1;i<=str.size();i++){
s[i][str[i-1]-'a']=1;
}
for(int i=0;i<26;i++){
for(int j=1;j<=str.size();j++){
s[j][i]+=s[j-1][i];
}
}
int q;
cin>>q;
while(q--){
int a,b,c,d;
cin>>a>>b>>c>>d;
if(check(a,b,c,d)){
cout<<"DA"<<endl;
}
else{
cout<<"NE"<<endl;
}
}
return 0;
}先把每个位置上出现的字母标记为 1。然后对每个字母做前缀和，s[j][i]就是前j个字符中第i个字母出现的总次数。最后对两个区间内出现的每个字母个数进行比较。这种方法通过预处理数组得到每一个字符前缀和，处理的时间复杂度是O(n)，可以方便后续的比较。
Acwing1230 K倍区间
给定一个长度为N的数列，$A_1,A_2,… A_N$,如果其中一段连续子序列$A_i,A_{i+1},…A_{j}$之和是K的倍数，我们就称区间[i,j]是K倍区间。请求出数列中一共有多少个K倍区间。
输入格式：第一行包含两个整数N和K。以下N行每行包含一个整数$A_{i}$。
输出格式：输出一个整数，代表K倍区间的数目。
题目分析
一个最简单的想法就是通过前缀和得到一个新的数组nums，然后用双循环来遍历这个新的数组，判断每个区间是否是K的倍数，这个复杂度是$O(n^2)$,绝对也会超时，这道题明显是希望我们可以找到一个方法，通过遍历一次数组就可以得到结果，我们可以对nums[i]对K取余，假如说nums[i]与nums[j]的余数一致，那说明[i,j]就是K倍区间。当我们遍历到nums[m]余数为a，只需要看前面有几个余数为a的即可。取余运算在这种算法题目中是非常常见的，一般可以多往这方面想想。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
int N,K;
cin>>N>>K;
vector<int>nums(N+1);
vector<int>sum(N+1);
long long ans=0;
vector<int>v(K);
for(int i=1;i<=N;i++){
cin>>nums[i];
sum[i]=(sum[i-1]+nums[i])%K;
ans+=v[sum[i]];
v[sum[i]]++;
}
cout<<ans+v[0]<<endl;
return 0;
}还需要注意的一小点就是余数为0的，本身就可以作为一个区间，所以最后需要再加上v[0]。
Acwing 3574乘积数量
给定一个长度为n且不包含0的整数序列$a_1,a_2,…,a_n$。请你计算以下两值：
1.使得$a_{l}×a_{l+1}×…×a_{r}$为负的索引对(l,r)(l<=r)的数量。
2.使得$a_{l}×a_{l+1}×…×a_{r}$为正的索引对(l,r)(l<=r)的数量。
输入格式：
第一行输入一个整数n。
第二行包含n个整数$a_1,…,a_n$。
输出格式：
输出单个空格隔开的两个整数，分别表示负的索引对数和正的索引对数。
数据范围:
$1 \leq n \leq 2×10^5$
$-10^9 \leq a_i \leq 10^9$
题目分析
在这到题里面，$a_i$只需要考虑是不是正的就行了，为了方便一些，我打算把大于0的全部都换成1，小于0的全部都换成-1，这道题里就不做前缀和了，直接前缀积，反正现在的数全部都是1和-1，相乘之后也只会是1和-1，假如nums[j]=-1,那我们可以看前面有几个nums[i]=-1，这样[i+1,j]就是正的索引对；相反，前面有几个nums[i]=1,这样[i+1,j]就是负的索引对；nums[j]=1也是类似的。
#include<iostream>
using namespace std;
const int N=2e5+1;
long long arr[N]={1};
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
if(arr[i]>0){
arr[i]=1;
}
else{
arr[i]=-1;
}
}
int plus=0;
int minus=0;
long long retp=0;
long long retm=0;
for(int i=1;i<=n;i++){
arr[i]=arr[i]*arr[i-1];
if(arr[i]>0){
retp+=plus;
retm+=minus;
plus++;
}
else{
retp+=minus;
retm+=plus;
minus++;
}
}
cout<<retm+minus<<" "<<retp+plus<<endl;
return 0;
}这道题和前面的那道K倍区间是类似的。
Acwing3493.最大的和
给定一个长度为n的正整数数列$a_1,a_2,…,a_n$。初始时，数列中的元素要么处于可选状态，要么处于不可选状态。
你可以选择一个长度恰好为k的区间[i,i+k-1]，使得$a_i \sim a_{i+k-1}$这k个元素的状态全部变为可选状态。
请问，在经过次操作之后，所有处于可选状态的元素之和最大是多少。
输入格式：
第一行包含两个整数n和k。
第二行包含n个整数$a_i$.
第三行包含一个长度为n的01序列，如果第i个数为1，表示$a_i$的初始状态为可选，如果第i个数为0，表示$a_i$的初始状态不可选。
输出格式：
一行一个整数，表示答案。
题目分析
简单而言，这道题目的意思就是有一个数组，目前只有部分元素使可选的，现在可以使一个长度为k的区间内的全部都变为可选，使处于可选状态的元素之和最大，
原来的数组可选部分的元素和是固定的，现在一个区间内的数组全部变为可选，也就是说这样会有一个增加量，想要元素之和最大，那么这个增加量需要是最大的。
此时，我们可以用两次前缀和，第一次就是对a[i]原数组，第二次是对a[i]*b[i],然后遍历一次数组，找到最大的增加量即可。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+1;
int n,k;
ll a[N],b[N];
ll aa[N]={0};
ll bb[N]={0};
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
aa[i]=aa[i-1]+a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
bb[i]=bb[i-1]+a[i]*b[i];
}
ll cha=0;
for(int j=k;j<=n;j++){
cha=max(cha,(aa[j]-aa[j-k])-(bb[j]-bb[j-k]));
}
cout<<cha+bb[n]<<endl;
return 0;
}Acwing5295
给定一个长度为n的整数数组$a_0,a_1,…,a_{n-1}$.
函数sum(l,r)的定义如下：
- 如果$l=r$,则$sum(l,r)=0$。
- 如果$l<r$，则$sum(l,r)=\sum_{i=l}^{r-1}a_{i}$。
请你找到一个三元组(x,y,z),要求：
- $0 \leq x \leq y \leq z \leq n$
- sum(0,x)-sum(x,y)+sum(y,z)-sum(z,n)的值是尽可能大的。
输入格式：
第一行包含整数n。
第二行包含n个整数$a_0,a_1,…,a_{n-1}$。
输出格式:
在一行内输出三个整数，表示满足条件的整数三元组(x,y,z)。
数据范围:
$1 \leq n \leq 5000,-10^9 \leq a_i \leq 10^9$。
题目分析
首先肯定是需要对原来的数组做前缀和的，接下来需要确定三个数，最直接的方法应该是叠加三个for循环，这个时间复杂度是$O(n^3)$，但肯定不会通过全部的测试用例。我们可以先确定中间的y，然后在(1,y)中寻找x使得sum(0,x)-sum(x,y)是最大的，然后在(y,n)中间寻找z，使得sum(y,z)-sum(z,n)是最大的，这样在确定y的条件下，就可以得到需要的最大值。为了得到整体的最大值，我们可以遍历整个数组来确定y，这样的时间复杂度是$O(n^2)$。
#include<iostream>
#include<vector>
using namespace std;
int n;
long long getSum(int l,int r,vector<long long>&nums){
return nums[r-1]-nums[l-1];
}
int main()
{
cin>>n;
vector<long long>nums(n+1);
for(int i=1;i<=n;i++){
cin>>nums[i];
}
for(int j=1;j<=n;j++)
{
nums[j]+=nums[j-1];
}
long long maxSum=-0x3f3f3f3f3f3f3f3f;
int x=1,y=1,z=1;
for(int yy=1;yy<=n+1;yy++){
long long res1=-0x3f3f3f3f3f3f3f3f;
long long res2=-0x3f3f3f3f3f3f3f3f;
int tx,tz;
for(int xx=1;xx<=yy;xx++){
long long tt=getSum(1,xx,nums)-getSum(xx,yy,nums);
if(tt>res1){
res1=tt;
tx=xx;
}
}
for(int zz=yy;zz<=n+1;zz++){
long long tt=getSum(yy,zz,nums)-getSum(zz,n+1,nums);
if(tt>res2){
res2=tt;
tz=zz;
}
}
if(res1+res2>maxSum){
maxSum=res1+res2;
x=tx;
y=yy;
z=tz;
}
}
cout<<x-1<<" "<<y-1<<" "<<z-1;
return 0;
} Acwing3956
给定一个长度为n的数组$a_1,a_2,…,a_n$。
现在，要将该数组从中间截断，得到三个非空子数组，要求三个子数组内各元素之和都相等。
请问，共有多少种不同的截断方法。
输入格式:
第一行包含整数n。
第二行包含n个整数$a_1,a_2,…,a_n$
输出格式：
输出一个整数，表示截断方法的数量。
数据范围:
$1 \leq n \leq 10^5,-10000 \leq a_i \leq 10000$。
题目分析：
得到 三个非空子数组的和都相等，说明数组的和需要是3的倍数才行。这道题大概率也是得找出遍历一遍前缀和数组就能得到结果的方法，那么每当我们遍历到nums[j]时，看其是否满足是nums[n]的三分之二，然后再看其前面有多少个nums[i]是nums[n]的三分之一倍，这样就要求在遍历数组的时候将是nums[n]的三分之一的nums[i]的个数存储起来。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n;
int main()
{
cin>>n;
vector<long long>nums(n+1);
for(int i=1;i<=n;i++){
cin>>nums[i];
nums[i]+=nums[i-1];
}
if(nums[n]%3!=0 || n<3){
cout<<0<<endl;
}
else{
int point=0;
long long ans=0;
for(int i=1;i<n;i++){
if(nums[i]==(nums[n]/3)*2){
ans+=point;
}
if(nums[i]==nums[n]/3){
point++;
}
}
cout<<ans;
}
}有一个需要注意的点就是下面这两个if判断语句的顺序不能颠倒，可以试想一种情况(0,0,0,0,0,0,0),一个数组全为0的话，如果将顺序颠倒就会出现一种情况：只分成了两个数组，而第三个是空的。
