题解 P1438 【无聊的数列】

· · 题解

正解应该是线段树，不过这题分块也能做。而且分块很好写，常数小。我只写了29行orz

首先，对于一个等差数列s+d,s+2d,s+3d\cdots ，随意抽取一段都是等差数列。比如说抽取s+ad,s+(a+1)d\cdots s+bd，这是一个以s+ad为首项，d为公差的等差数列。

其次，对于两个等差数列s_{1},s_{1}+d_{1},s_{1}+2d_{1}\cdots 和 s_{2},s_{2}+d_{2},s_{2}+2d_{2}，叠加在一起为(s_{1}+s_{2}),(s_{1}+s_{2})+(d_{1}+d_{2}),(s_{1}+s_{2})+2(d_{1}+d_{2})\cdots 这是一个以(s_{1}+s_{2})为首项，(d_{1}+d_{2})为公差的等差数列。也就是说，等差数列可以叠加。

因此，对每一个块x，可以维护加在整个块上的等差数列的首项S[d]及公差D[d]。对于没有完整覆盖这个块的等差数列，其数的个数不超过2\sqrt{n}个，直接暴力修改。查询时直接查询a[i]的值加上i所在块的首项，加上其公差乘以i与块端点的距离。

代码：（960+ms）

#include<cstdio>
#include<cmath>
const int maxn=100005,sqrn=350;
int a[maxn],bel[maxn],le[sqrn],ri[sqrn],S[sqrn],D[sqrn],block,n,m,cnt,l,r,s,d,p;
void add(int l,int r,int s,int d)
{
    if(bel[l]==bel[r])for(register int i=l;i<=r;++i)a[i]+=s+(i-l)*d;
    else
    {
        int L=ri[bel[l]],R=le[bel[r]];
        for(register int i=l;i<=L;++i)a[i]+=s+(i-l)*d;
        for(register int i=R;i<=r;++i)a[i]+=s+(i-l)*d;
        for(register int i=bel[l]+1;i<bel[r];++i)S[i]+=s+(le[i]-l)*d,D[i]+=d;
    }
}
int main()
{
    scanf("%d%d",&n,&m);for(register int i=1;i<=n;++i)scanf("%d",a+i);
    block=sqrt(n);cnt=n/block;if(n%block)++cnt;
    for(register int i=1;i<=n;++i)bel[i]=(i-1)/block+1;
    for(register int i=1;i<=cnt;++i)le[i]=(i-1)*block+1,ri[i]=i*block;ri[cnt]=n;
    while(m--)
    {
        scanf("%d",&p);
        if(p==1)scanf("%d%d%d%d",&l,&r,&s,&d),add(l,r,s,d);
        else scanf("%d",&l),printf("%d\n",a[l]+S[bel[l]]+D[bel[l]]*(l-le[bel[l]]));
    }
    return 0;
}