OI

【前缀和】k倍区间、前缀和相关

前缀和是一项很强的优化技巧了，它可以瞬间将区间求和从$O(n)$降到$O(1)$。然而对于有些复杂度很高的题，就可能要在前缀和的基础上再加些思考了。

P1714切蛋糕
这道题的最朴素算法是枚举区间、循环求和的$O(n^3)$算法，在这里显然是不行的。很自然地想到用前缀和优化降成$O(n^2)$。
然而此题的n=500000，非常大，$O(n^2)$也是不行的，必须进一步优化。这里就可以在前缀和上动一些手脚了。
可以发现，整个枚举区间的过程（n方）其实就是在i-m<=j<=i里找到前缀和数组中$s_j$的最小值，此时就一目了然了，使用其他数据结构维护就可以优化这个枚举寻找最小值的过程了。
于是使用线段树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=600005;
const int MAX=2147483647;
int s[MAXN]={0};
int sgt[4*MAXN]={0};

void build(int rt,int st,int ed){
    if(st==ed){
        sgt[rt]=s[st];
        return;
    }
    int mid=(st+ed)/2;
    build(rt*2,st,mid);
    build(rt*2+1,mid+1,ed);
    sgt[rt]=min(sgt[rt*2],sgt[rt*2+1]);
}

int query(int rt,int nst,int ned,int qst,int qed){
    if(qst>ned||qed<nst)
        return MAX;
    if(qst<=nst&&qed>=ned)
        return sgt[rt];
    int mid=(nst+ned)/2;
    return min(query(rt*2,nst,mid,qst,qed),query(rt*2+1,mid+1,ned,qst,qed));
    
}

int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int i,t;
    for(i=1;i<=n;i++){
        scanf("%d",&t);
        s[i]=s[i-1]+t;
    }
    
    build(1,1,n);
    
    int s1,s2,ans=0;
    
    for(i=1;i<=n;i++){
        s2=query(1,1,n,i-k,i);
        t=s[i]-s2;
        if(t>ans)ans=t;
    }
    
    printf("%d",ans);
    return 0;
}

可以看到，此题需要运用前缀和的性质才能进行进一步优化，最后达到从$O(n^3)$到$O(n^2)$最后到$O(nlogn)$的过程。

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

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

此题和上题类似，如果枚举区间将是$O(n^3)$的算法，而经过前缀和优化可以降到$O(n^2)$。那么，能不能进一步优化呢？
同样从前缀和数组出发，发现每一次计算的$$sum_{[i,j]}=s_i-s_{j-1}$$那么$sum$ $mod$ $k=0$等价于$s_i$ $mod$ $k=s_j$ $mod$ $k$
此时，只要预处理前缀和数组，记录前缀和%k的值。这样，如果模数相等就是一个区间，特别的，模为0的点不仅可以组成区间，自己本身也是一个k倍区间，记录答案时要单独加上。那么，再建立数组$cnt$，记录每一个模数出现的次数$cnt_i$，那么区间个数就是$C^2_{cnt_i}$。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
const int MAXN=100005;
int s[MAXN]={0},cnt[MAXN]={0};

int main(){
    int n,k,t,i,j;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&t);
        s[i]=(s[i-1]+t)%k;
        cnt[s[i]]++;
    }
    
    int ans=0;
    ans+=cnt[0];
    for(i=0;i<k;i++){
        ans+=(cnt[i]-1)*cnt[i]/2;
    }
    
    printf("%d",ans);
    
    return 0;
}

复杂度$O(n+k)$。

P3941 入阵曲
此题是k倍区间的应用。题意大致为k倍矩阵的个数。
其实就是把k倍区间二维化了。所以，如果是朴素的二维前缀和枚举子矩阵将会是$O(n^4)$，显然是无法接受的。
此题的思路是：将矩阵降维成区间，再用k倍区间的方法处理。
先按一个维度枚举，如枚举1<=j<=i<=n，确定矩阵的上下界。朴素算法中，到这里就要枚举左右界了。此时，上下界之间的范围内可以看作一个一维的区间；再使用二维前缀和可以算出那个上下界范围内的前缀和（一位数组）。这时，我们就用一个数组表示了这个矩阵区间，接下来在这个区间上使用k倍区间算法算出上下界间的区间个数，就是要求的这一宽度的k倍矩阵数了。
然而此题的复杂度要求很高，即使这样也是$O(n^2(m+k))$，k还是比较大的数。于是这里还要在cnt数组计数时记录被修改过的地方，计算时直接访问，在k较大时这个循环会远小于k，最终达到优化的目的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;
typedef long long ll;
const int MAXN=405;
const int MAXK=1000005; 

ll s[MAXN][MAXN]={0};
int cnt[MAXK]={0};
bool vis[MAXK]={0};

int main(){
    int n,m,kk;
    scanf("%d%d%d",&n,&m,&kk);
    int i,j,k,t;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            scanf("%d",&t);
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+t;
        }
    ll ans=0;
    stack<int> st;
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++){
            for(k=1;k<=m;k++){
                t=(s[i][k]-s[j-1][k])%kk;
                cnt[t]++;
                if(!vis[t]){
                    st.push(t);
                    vis[t]=1;
                }
            }
            ans+=cnt[0];
            
            while(!st.empty()){
                t=st.top();
                ans+=(cnt[t]*(cnt[t]-1))>>1;
                cnt[t]=0;
                vis[t]=0;
                st.pop();
            }
            
        }
    
    printf("%lld",ans);
    return 0;
}