题目内容

P1438

大意:维护一个序列,支持区间加等差数列以及单点查询操作

解题思路

注意等数列:等差数列的差分是相等的,所以我们可以维护一个原数列的差分,每一次加等差数列的时候进行区间加公差以及两端点修改就可以了:

假设要加上去的数列首项为 K,公差为 D,要加上去的区间为 [l,r]p 为原序列的差分,则有 p_l\leftarrow Kp_{[l+1,r]}\leftarrow p_{[l+1,r]}+D,至于最后一项,肯定是要还原回去的原来加了多少现在就要还回去多少,所以 p_{r+1}\leftarrow p_{r+1}-K-(r-l)D

  • 注意如果 r=n 的话不能进行最后一个操作
  • 注意如果 l=r 的话不能进行第二个操作

除此之外坑点就没有了,观察 p 数组,我们要进行的是区间修改和区间查询工作,所以线段树可以解决这个问题(虽然树状数组也可以),代码如下:

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

const int maxn=1e5+5;
int f[maxn<<2],tag[maxn<<2],a[maxn],n,m;

inline int read()
{
    bool w=0;
    int x=0;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            w=1;
        c=getchar();
    }
    while(isdigit(c))
        x=x*10+c-'0',c=getchar();
    return w?-x:x;
}

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

void down(int i,int j,int k)
{
    f[L]+=tag[k]*(M-i+1);
    f[R]+=tag[k]*(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]+=(j-i+1)*d;
        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;
}

int 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);
    int 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);
    int opt,l,r,k,d,p;
    while(m--)
    {
        opt=read();
        if(opt==1)
        {
            l=read(),r=read(),k=read(),d=read();
            modify(1,n,l,l,1,k);
            if(l+1<=r)
                modify(1,n,l+1,r,1,d);
            if(r<n)
                modify(1,n,r+1,r+1,1,-((r-l)*d+k));
        }
        else
        {
            p=read();
            printf("%d\n",ask(1,n,1,p,1));
        }
    }
    return 0;
}
最后修改日期:2020年3月12日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。