题解 P1438 【无聊的数列】

windows250 · 2017-10-23 17:00:10 · 题解

其实这是道线段树的模板题:

• 首先我们容易联想到等差数列的一个性质:An - An-1=d,于是容易想到用差分去解这道题。

• 那么怎么差分呢?我们先读入给定的等差数列s,然后再开一个数组sum记录差分,每次1号操作有L,R,D,K四个参数,而我们需要进行的操作其实很简单:

1.对于L:sum[L]=sum[L]+K,

2.对于区间(L,R]:sum[i]=sum[i]+D,i∈(L,R],

3.对于R+1:sum[R+1]=sum[R+1]-(K+((R-L)*D).

• 而对于每次查询P的值,只要输出 s[P]+sum[1]+...+sum[P] 的值即可。

再回头看看我们需要维护的差分数组的特征,

这不就是 区间修改+区间求和 的模板吗？？？

详细见代码:

#include<iostream>
#include<cstdio>
#define ls root<<1,l,mid
#define rs root<<1|1,mid+1,r
#define MAXN 100001

using namespace std;

int n,m;
int s[MAXN],sum[MAXN<<2],lazy[MAXN<<2];

inline void push_up(int root)
{
    sum[root]=sum[root<<1]+sum[root<<1|1];
}

inline void push_down(int root,int len)
{
    if(lazy[root])
    {
        lazy[root<<1]+=lazy[root];
        lazy[root<<1|1]+=lazy[root];
        sum[root<<1]+=(len-(len>>1))*lazy[root];
        sum[root<<1|1]+=(len>>1)*lazy[root];
        lazy[root]=0;
    }
}

inline void update(int root,int l,int r,int L,int R,int val)
{
    if(L<=l && r<=R){sum[root]+=(r-l+1)*val;lazy[root]+=val;return;}
    push_down(root,r-l+1);
    int mid=(l+r)>>1;
    if(mid>=L) update(ls,L,R,val);
    if(mid<R) update(rs,L,R,val);
    push_up(root);
}

inline int query(int root,int l,int r,int L,int R)
{
    if(L<=l && r<=R) return sum[root];
    push_down(root,r-l+1);
    int mid=(l+r)>>1;int total=0;
    if(mid>=L) total+=query(ls,L,R);
    if(mid<R) total+=query(rs,L,R);
    return total;
}

int main()
{
    in(n),in(m);
    for(int i=1;i<=n;i++) in(s[i]);
    int type,L,R,K,D,ask;
    while(m--)
    {
        in(type);
        if(type==1)
        {
            in(L),in(R),in(K),in(D);
            update(1,1,n,L,L,K);
            if(R>L) update(1,1,n,L+1,R,D);
            int N=R-L+1;
            if(R!=n) update(1,1,n,R+1,R+1,-(K+(N-1)*D));
        }
        else
        {
            in(ask);
            printf("%d\n",s[ask]+query(1,1,n,1,ask));
        }
    }
    return 0;
}
//By windows250