洛谷 P1438 无聊的数列 题解

原题链接

首先，我们考虑用差分解决问题。

用 \(x_i\) 表示原数列，\(a_i = x_i - x_{i-1}\)

那么，先普及一下差分：

如果我们只需要维护区间加值，单点求值的话，你会发现两个重要等式：

\[a_i = x_i - x_{i-1}\]

\[\sum_{j=1}^i a_j = x_i\]

我们每次修改 \(l,r\) 区间增加 \(k\) 的话，你会发现：

则 \(l+1,r\) 这一段，所有的 \(a_i\) 都是不变的。这是因为：

\[(x_i + k) - (x_{i-1} + k) = x_i - x_{i-1} = a_i\]

那么对于 \(a_l\) 这个点，显然：

\[(x_l + k) - x_{l-1} = (x_l - x_{l-1}) + k = a_l + k\]

对于 \(a_{r+1}\) 这个点，显然：

\[a_{r+1} - (a_r + k) = (a_{r+1} - a_r) - k = a_{r+1} - k\]

这是正常的差分。

可是，我们现在加上了一个 等差数列 。由于等差数列的性质，显然每个点加上的值比前一个点多 \(d\).

所以， \(l+1 , r\) 这一段， \(a_i \gets a_i + d\) .

那么对于 \(a_l\) 这个点：

\[(x_l + k) - x_{l-1} = (x_l - x_{l-1}) + k = a_i + k\]

对于 \(a_{r+1}\) 这个点：

\[x_{r+1} - (x_r + k + (r-l) \times d) = (x_{r+1} - x_r) - (k + (r-l) \times d) = a_{r+1} - (k + (r-l) \times d)\]

下面我们考虑单点查询。

\[x_i = \sum_{j=1}^i a_j\]

显然，我们用 线段树 维护 \(x\) 数组的区间修改和区间求和。

时间复杂度： \(O(n \log n + m \log n)\).

空间复杂度： \(O(n)\).

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1e5+1;
#define L (i<<1)
#define R i<<1|1 

inline ll read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
    ll x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

struct tree{
    int l,r; ll tag;
    ll sumi;
};
tree t[4*N];
int n,m,x[N]; //原数组
ll a[N];      //差分后的数组

inline void update(int i) {
    t[i].sumi=t[L].sumi+t[R].sumi;
} //更新

inline void pass(int i,ll x) {
    t[i].tag+=x;
    t[i].sumi+=x*(t[i].r-t[i].l+1);
}

inline void pushdown(int i) {
    pass(L,t[i].tag);
    pass(R,t[i].tag);
    t[i].tag=0;
} //下传标记

inline void build_tree(int i,int l,int r) {
    t[i].l=l; t[i].r=r;
    if(l==r) {
        t[i].sumi=a[l]; t[i].tag=0;
        return;
    } int mid=(l+r)>>1;
    build_tree(L,l,mid);
    build_tree(R,mid+1,r);
    update(i);
} //建树

inline ll query(int i,int l,int r) {
    if(l<=t[i].l && t[i].r<=r) return t[i].sumi;
    int mid=(t[i].l+t[i].r)>>1; ll ans=0;
    pushdown(i);
    if(l<=mid) ans+=query(L,l,r);
    if(r>mid) ans+=query(R,l,r);
    return ans; 
} //询问

inline void change(int i,int l,int r,int x) {
    if(l<=t[i].l && t[i].r<=r) {
        t[i].sumi+=x*(t[i].r-t[i].l+1);
        t[i].tag+=x; return ;
    } pushdown(i);
    int mid=(t[i].l+t[i].r)>>1;
    if(l<=mid) change(L,l,r,x);
    if(r>mid) change(R,l,r,x);
    update(i);
} //修改

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) x[i]=read();
    for(int i=1;i<=n;i++) a[i]=ll(x[i]-x[i-1]);
//  for(int i=1;i<=n;i++) printf("%d ",a[i]);
//  putchar('\n');
    build_tree(1,1,n);
    while(m--) {
        int opt=read();
        ll l,r,k,d;
        if(opt==1) {
            l=read(),r=read(),k=read(),d=read();
            change(1,l,l,k);
            if(r>l) change(1,l+1,r,d); 
            if(r-n) change(1,r+1,r+1,-(k+(r-l)*d));
                        //维护 
        } else printf("%lld\n",query(1,1,read()));
    }
    return 0;
}

洛谷 P1438 无聊的数列 题解

原文：https://www.cnblogs.com/bifanwen/p/12503434.html