P1438 无聊的数列（线段树+差分）

秒速五厘米 2021-12-03 04:13 249阅读 0赞

## 题意：给一个区间加一个，首项为k，公差为d 的等差序列，求单点值。   分析：先建一颗差分线段树，如果我们给某一个区间 l 到 r 加上一个首相为k 公差为d 的等差序列，相当于 给 l 这个点的差分数组 加上 k，l+1 到 r 的这段数组 加上d，r+1 这个点差分数组加上 -(k+(r-l+1-1)\*d)，然后再利用差分数组的前缀和恰好等于这个点的值 ，利用线段树进行区间求和就好了，这样问题就变成了线段树区间修改+区间求和的模板。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e6+11;
    int a[N],sum[N],lazy[N];
    
    void pushup(int i)
    {
        sum[i] = sum[i<<1]+sum[i<<1|1];
    }
    
    void pushdown(int i,int l,int r)
    {
        int mid = (l+r)>>1;
        if(!lazy[i])return;
        sum[i<<1] += (mid-l+1)*lazy[i];
        sum[i<<1|1] += (r - mid)*lazy[i];
        lazy[i<<1] += lazy[i];
        lazy[i<<1|1] += lazy[i];
        lazy[i] = 0;
    }
    
    void build(int o,int l,int r) {
        if(l>=r) {
            sum[o]=a[l];
            return ;
        }
        int m=(l+r)/2;
        build(2*o,l,m);
        build(2*o+1,m+1,r);
        pushup(o);
    }
    
    void update(int i,int l,int r,int ql,int qr,int v)
    {
        if(ql <= l && qr >= r)
        {
            sum[i] += v*(r-l+1);
            lazy[i] += v;
            return;
        }
        pushdown(i,l,r);
        int mid = (l+r)>>1;
        if(ql<=mid)update(i<<1,l,mid,ql,qr,v);
        if(qr>mid)update(i<<1|1,mid+1,r,ql,qr,v);
        pushup(i);
    }
    
    int query(int i,int l,int r,int ql,int qr)
    {
        if(ql<=l && qr>=r)return sum[i];
        pushdown(i,l,r);
        int mid = (l+r)>>1;
        int ans = 0;
        if(ql<=mid)ans+=query(i<<1,l,mid,ql,qr);
        if(qr>mid)ans+=query(i<<1|1,mid+1,r,ql,qr);
        return ans;
    }
    
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=n;i>=1;i--)
            a[i]=a[i]-a[i-1];
        build(1,1,n);
        for(int i=1;i<=m;i++)
        {
            int op,l;
            scanf("%d%d",&op,&l);
            if(op == 1)
            {
                int r,k,d;
                scanf("%d%d%d",&r,&k,&d);
                update(1,1,n,l,l,k);
                if(r!=n)update(1,1,n,r+1,r+1,-(k+(r-l)*d));
                if(r>l)update(1,1,n,l+1,r,d);
            }
            else printf("%d\n",query(1,1,n,1,l));
        }
        return 0;
    }