解题报告 P4868 Preprefix sum

题目内容

P4868

大意:维护一串序列,支持单点修改和前前缀和查询(\displaystyle\sum_{k=1}^i\sum_{j=1}^ka_j

解题思路

前前缀和,就是前缀和的前缀和,既然需要查询前前缀和,那么就可以想到维护序列的前缀和,查询的时候区间查询 [1,i],修改的时候由于修改一个特定位置的数,后面的所有前缀和都会被影响,所以相当于区间修改前缀和,区间修改区间查询,很容易想到使用线段树维护。

当然用差分处理了的树状数组也可以,但是线段树明显好理解。

要注意的细节:

  • 建线段树的时候记得是记录前缀和
  • 修改 a_ix 的时候相当于 (i,n] 的前缀和都要加上 x-a_i,所以 a_i 一定要存下来

代码:

#include <cstdio>
#include <cctype>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)
typedef long long ll;

const int maxn=100005;
ll a[maxn],s[maxn],f[maxn<<2],tag[maxn<<2];

int n,m;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

void build(int i,int j,int k)
{
    if(i==j)
    {
        a[i]=read();
        s[i]=s[i-1]+a[i];
        f[k]=s[i];
        return;
    }
    build(i,M,L);
    build(M+1,j,R);
    f[k]=f[L]+f[R];
    return;
}

inline void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1ll);
    f[R]+=tag[k]*(ll)(j-M);
    tag[L]+=tag[k];
    tag[R]+=tag[k];
    tag[k]=0;
    return;
}

void modify(int i,int j,int l,int r,int k,int d)
{
    if(i>=l && j<=r)
    {
        f[k]+=d*(j-i+1ll);
        tag[k]+=d;
        return;
    }
    if(tag[k])
        down(i,j,k);
    if(l<=M)
        modify(i,M,l,r,L,d);
    if(r>M)
        modify(M+1,j,l,r,R,d);
    f[k]=f[L]+f[R];
    return;
}

ll ask(int i,int j,int l,int r,int k)
{
    if(i>=l && j<=r)
        return f[k];
    if(tag[k])
        down(i,j,k);
    ll ans=0;
    if(l<=M)
        ans+=ask(i,M,l,r,L);
    if(r>M)
        ans+=ask(M+1,j,l,r,R);
    return ans;
}

int main()
{
    n=read(),m=read();
    build(1,n,1);
    char opt[10];
    int i;
    while(m--)
    {
        scanf("%s %d",opt,&i);
        if(opt[0]=='M')
        {
            ll x=read();
            modify(1,n,i,n,1,x-a[i]);
            a[i]=x;
        }
        else
            printf("%lld\n",ask(1,n,1,i,1));
    }
    return 0;
}

解题报告 P1719 最大加权矩形

题目内容

P1719

大意:给定一个数字矩阵,求最大子矩阵和

解题思路

这题可以使用最大子段和的思想,思想就是合并矩阵,将其降维打击。

每次枚举待合并矩阵的行的上下界,然后开数组将这几行上的数合并,然后取最大子段和。这就是将矩阵降维。

复杂度:枚举上下界的过程是 O(n^2) 的,合并的过程是 O(n^2),使用前缀和优化后为 O(n),求最大子段和的复杂度是 O(n),因此总的复杂度是 O(n^3)。具体见代码:

#include <cstdio>
#include <cstring>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=125;
int n,s[maxn][maxn],a[maxn][maxn],f[maxn],tmp[maxn];
//s[i][j]存储矩阵第j列的前i行的前缀和,tmp存储合并后的结果,f为dp使用

int getsum()//求最大子段和的
{
    memset(f,0,sizeof(f));//先清零
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        f[i]=max(f[i-1]+tmp[i],f[i]);//求最大子段和
        ans=max(ans,f[i]);
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            s[i][j]+=s[i-1][j]+a[i][j];//处理这一列的前缀和
        }
    int ans=0;
    for(int i=1;i<=n;i++)//i为上界
        for(int j=i;j<=n;j++)//j为下界
        {
            for(int k=1;k<=n;k++)//O(n)合并
                tmp[k]=s[j][k]-s[i-1][k];
            ans=max(ans,getsum());//统计答案
        }
    printf("%d\n",ans);
    return 0;
}

解题报告 P1182 数列分段 Section II

题目内容

P1182

大意:给出一个序列,要求分成 m 段,求每段和的最大值的最小值

解题思路

一看到“最大的最小”就知道这题需要使用二分答案。首先判断他的单调性:很明显,我们如果设定每段和的最大值越大,需要划分的段数就越小,相反的,如果我们设定每段和的最大值越小,需要划分的段数就越多,以此性质来进行二分答案。

至于如何判断,就需要使用前缀和,具体见代码的 check 函数。

#include <cstdio>

const int maxn=1e5+5;
int n,m,a[maxn],sum[maxn];

bool check(int mid)
{
    int cnt=0,lastans=1;//cnt为切的刀数,lastans为新一段的起点
    for(int i=1;i<=n;i++)//开始扫描
    {
        if(sum[i]-sum[lastans-1]>mid)//如果[lastans,i]的和大于设定的最大值
        {
            cnt++;//那么就只取[lastans,i-1]
            lastans=i;//i成为新的lastans
        }
    }
    return cnt+1<=m;//由于cnt是刀数,判断的时候要+1
}

int main()
{
    scanf("%d %d",&n,&m);
    int maxa=0;//序列中元素的最大值,以此为左端点进行二分
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        sum[i]=sum[i-1]+a[i];
        maxa=maxa<a[i]?a[i]:maxa;
    }
    int l=maxa,r=sum[n],ans;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))//如果能行,就说明mid可以再小一点
        {
            ans=mid;
            r=mid;
        }
        else
            l=mid+1;
    }
    printf("%d\n",ans);
}

总的时间复杂度为 O(n\log n)

解题报告 P3406 海底高铁

题目内容

P3406

大意:一个高铁,每段路有票和IC卡两种选择,问最少费用

解题思路

嗯,这题的思路不太好想,看似dp实际上不是。要求最小费用,就涉及到买卡还是买票的决策。而买票还是买卡取决于通过这段铁路的次数。又由于主人公是在各个城市间到处晃,所以可以开一个差分数组记录每段铁路通过的次数。

使用差分数组时,相当于区间加,然后确定铁路的通过次数后就可以计算是买卡省钱还是买票省钱。时间复杂度O(n),看似常数较大,但是实际跑得飞快,不开读优不吸氧可以155ms)

细节:
– 要开long long,不然会炸(最坏情况1e6*1e6会爆int)
– 由于i铁路连接i和i+1,所以在差分时右端点不用加1

代码:

#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxn=1e5+5;
int n,m;
ll p[maxn],a[maxn],b[maxn],c[maxn];
ll time[maxn];//每条铁路乘坐次数的差分数组
//i铁路连接i和i+1

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%lld",&p[i]);
    for(int i=1;i<n;i++)
        scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
    for(int i=1;i<m;i++)
    {
        int l=min(p[i],p[i+1]),r=max(p[i],p[i+1]);//注意判断l和r的大小
        time[l]++,time[r]--;//由于i铁路连接i和i+1,所以r不要加一
    }
    ll ans=0;
    for(int i=1;i<=n;i++)//进入决策环节
    {
        time[i]+=time[i-1];//把差分加上来获取源数据
        if(a[i]*time[i]>c[i]+b[i]*time[i])//做比较
            ans+=c[i]+b[i]*time[i];
        else
            ans+=a[i]*time[i];
    }
    printf("%lld\n",ans);
}