P1438 无聊的数列

简要题意

给定一个序列 $a$，要求进行两种操作。

  • 对于区间 $[l,r]$ 对应加上一个长为 $r - l +1$，首项为 $K$，公差为 $D$ 的等差数列；
  • 查询第 $p$ 个数的值。

策略分析

题目要求将一段等差数列加到一段区间上去。我们一眼丁真想到了线段树，但是对于加的不是同一个值的情况，朴素的做法只能进行单点修改，如果这样单点改下去再单点查，和直接在数组上模拟没有任何区别，我们写线段树不光要多递归几层还很废空间。

遇到这种一眼就是线段树却不知道如何维护的题，我们就需要重新再回去审题来寻找操作的特殊性质。我们发现这道题的特殊性质就是等差数列。那么等差数列有什么性质呢？等差数列等差。虽然说这是一句废话，但是却恰恰揭示了这道题的关键，等差数列的差分序列中的值除了开头结尾以外完全相同。我们发现，对于一个从 $l$ 位置开始到 $r$ 位置结束的公差为 $d$ 的等差数列的差分序列有如下性质：

  • 对于位置 $l$ ，它的值一定等于等差数列的首项；
  • 对于位置区间 $[l + 1, r]$ 内的每个位置，它的值一定等于公差 $d$；
  • 对于位置 $r + 1$，它的值一定等于等差数列的末项。

有了这三个性质后，我们就可以把题目变成对原序列的差分序列进行一次区间加和两次单点修改，时间复杂度就大大缩减了。而单点求值其实就是求差分序列的前缀和，这样我们就可以做了，但是有如下细节需要注意：

  • 由于差分序列要修改 $r + 1$ 位置，所以不难发现我们建树的区间不是 $[1,n]$ 而是 $[1, n + 1]$；
  • 题目给的数据范围很有迷惑性，容易给人造成不用开 long long 的假象，然而如果不开就会 WA on 1st；
  • 题目给的修改区间存在数据使得 $l=r$，此时我们 update(1, l + 1, r, d); 这句就会 RE，需要特判。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#define LL long long
#define ls ro << 1
#define rs ro << 1 | 1
using namespace std;

namespace SHAWN {
    const int N = 1e5 + 7;
    struct tree { int l, r; LL sum, tag; }tree[N << 2];
    int n, m;
    LL a[N];
    void pushup(int ro) { tree[ro].sum = tree[ls].sum + tree[rs].sum; }
    void build(int ro, int l, int r) {
        tree[ro].l = l; tree[ro].r = r;
        tree[ro].tag = 0;
        if (l >= r) {
            tree[ro].sum = a[l] - a[l - 1];
            return;
        }
        int mid = l + ((r - l) >> 1);
        build(ls, l, mid); build(rs, mid + 1, r);
        pushup(ro);
    }
    void pushdown(int ro) {
        if (tree[ro].tag) {
            tree[ls].sum += (tree[ls].r - tree[ls].l + 1) * tree[ro].tag;
            tree[rs].sum += (tree[rs].r - tree[rs].l + 1) * tree[ro].tag;
            tree[ls].tag += tree[ro].tag;
            tree[rs].tag += tree[ro].tag;
            tree[ro].tag = 0;
        }
    }
    void update(int ro, int l, int r, LL x) {
        int lt = tree[ro].l, rt = tree[ro].r;
        if (l <= lt && r >= rt) {
            tree[ro].sum += (rt - lt + 1) * x;
            tree[ro].tag += x;
            return;
        }
        pushdown(ro);
        int mid = lt + ((rt - lt) >> 1);
        if (l <= mid) { update(ls, l, r, x); }
        if (r > mid) { update(rs, l, r, x); }
        pushup(ro);
    }
    LL getsum(int ro, int l, int r) {
        int lt = tree[ro].l, rt = tree[ro].r;
        if (l <= lt && r >= rt) { return tree[ro].sum; }
        pushdown(ro);
        int mid = lt + ((rt - lt) >> 1); LL res = 0;
        if (l <= mid) { res += getsum(ls, l, r); }
        if (r > mid) { res += getsum(rs, l, r); }
        return res;
    }
    signed work()
    {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) { cin >> a[i]; }
        build(1, 1, n + 1);
        while (m--) {
            int opt; cin >> opt;
            if (opt == 1) { 
                int l, r; LL k, d; cin >> l >> r >> k >> d;
                if (l != r) {
                    update(1, l, l, k);
                    update(1, l + 1, r, d);
                    update(1, r + 1, r + 1, -((r - l) * d + k));
                }
                else { 
                    update(1, l, l, k); 
                    update(1, r + 1, r + 1, -k);
                }
            }
            else if (opt == 2) {
                int p; cin >> p;
                cout << getsum(1, 1, p) << '\n';
            }
        }
        return 0;
    }
}

signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

说些什么吧！

twikoo