洛谷P1438 无聊的数列题解

题意：

维护一个数列 $a_i$，支持两种操作：

1 l r K D：给出一个长度等于 $r-l+1$ 的等差数列，首项为 $K$，公差为 $D$，并将它对应加到 $[l,r]$ 范围中的每一个数上。即：令 $a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D$。

2 p：询问序列的第 $p$ 个数的值 $a_p$。

输入格式：

第一行两个整数数 $n,m$ 表示数列长度和操作个数。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i$。

接下来的 $m$ 行，每行先输入一个整数 $\mathtt{op}$。

若 $\mathtt{op}=1$ 则再输入四个整数 $l,r,s,d$；

若 $\mathtt{op}=2$ 则再输入一个整数 $p$。

输出格式：

对于每个询问，一行一个整数表示答案。

数据范围：

$0\le n,m \le 10^5,~-200\le a_i,s,d\le 200,~1 \leq l \leq r \leq n,~1 \leq p \leq n$

区间加等差数列，直接维护原数组并不方便，因此考虑维护差分数组。

此时区间加等差数列的操作就变成了两个单点加和一个区间加，考虑线段树维护

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n,Q,a[N], val[N * 4], tag[N * 4];
void push_up(int at) { val[at] = val[ls(at)] + val[rs(at)]; }
void build(int l = 1,int r = n,int at = 1)
{
    if(l == r) { val[at] = a[l]; return; } int mid = (l + r) >> 1;
    build(l, mid, ls(at)); build(mid+1, r, rs(at)); push_up(at);
}
void push_down(int l,int r,int at)
{
    if(tag[at])
    {
        int mid = (l + r) >> 1;
        val[ls(at)] += tag[at] * (mid - l + 1); tag[ls(at)] += tag[at];
        val[rs(at)] += tag[at] * (r - mid); tag[rs(at)] += tag[at];
        tag[at] = 0;
    }
}
void Modify(int x,int k,int l = 1,int r = n,int at = 1)
{
    if(l == r) { val[at] += k; return; }
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(x <= mid) Modify(x, k, l, mid, ls(at));
    else Modify(x, k, mid + 1, r, rs(at));
    push_up(at);
}
void update(int nl,int nr,int k, int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) { val[at] += k * (r - l + 1); tag[at] += k; return; }
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, k, l, mid, ls(at));
    if(nr > mid) update(nl, nr, k, mid + 1, r, rs(at));
    push_up(at);
}
int query(int nl,int nr,int l = 1,int r = n,int at = 1)
{
    if(nl <= l && r <= nr) return val[at];
    push_down(l,r,at); int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return query(nl, nr, l, mid, ls(at)) + query(nl, nr, mid + 1, r, rs(at));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = n - 1; i; i--) a[i + 1] = a[i + 1] - a[i];
    build();
    for(int op,l,r,s,d,e,p; Q; Q--)
    {
        if(cin >> op, op == 1)
        {
            cin >> l >> r >> s >> d; e = s + d * (r - l);
            Modify(l, s);
            if(l + 1 <= r) update(l + 1, r, d);
            if(r < n) Modify(r + 1, -e);
        }else { cin >> p; cout << query(1, p) << '\n'; }
    }
    return 0;
}