LC 1622. 奇妙序列

题目描述

这是 LeetCode 上的 1629. 按键持续时间最长的键 ，难度为 困难。

请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。

请实现 Fancy 类 ：

  • Fancy() 初始化一个空序列对象。
  • void append(val) 将整数 val 添加在序列末尾。
  • void addAll(inc) 将所有序列中的现有数值都增加 inc 。
  • void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
  • int getIndex(idx) 得到下标为 idx 处的数值（下标从 $0$ 开始），并将结果对 $10^9 + 7$ 取余。如果下标大于等于序列的长度，请返回 $-1$ 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输入：
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]

输出：
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释：
Fancy fancy = new Fancy();
fancy.append(2);   // 奇妙序列：[2]
fancy.addAll(3);   // 奇妙序列：[2+3] -> [5]
fancy.append(7);   // 奇妙序列：[5, 7]
fancy.multAll(2);  // 奇妙序列：[5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3);   // 奇妙序列：[10+3, 14+3] -> [13, 17]
fancy.append(10);  // 奇妙序列：[13, 17, 10]
fancy.multAll(2);  // 奇妙序列：[13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20

提示：

  • $1 <= val, inc, m <= 100$
  • $0 <= idx <= 10^5$
  • 总共最多会有 $10^5$ 次对 append，addAll，multAll 和 getIndex 的调用。

线段树（多个懒标记）

代码：

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
class Fancy {
    class Node {
        int ls, rs;
        long val, add, mul = 1;
    }
    int N = (int) 1e8 + 10, M = 1000010, loc = 1, cnt = 0, mod = (int)1e9+7;
    Node[] tr = new Node[M];
    void add(int u, int lc, int rc, int l, int r, int v) {
        int len = rc - lc + 1;
        if (l <= lc && rc <= r) {
            tr[u].val += len * v; tr[u].val %= mod;
            tr[u].add += v; tr[u].add %= mod;
            return ;
        }
        pushdown(u, len);
        int mid = lc + rc >> 1;
        if (l <= mid) add(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) add(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    void mul(int u, int lc, int rc, int l, int r, int v) {
        if (l <= lc && rc <= r) {
            tr[u].val *= v; tr[u].val %= mod;
            tr[u].mul *= v; tr[u].mul %= mod;
            tr[u].add *= v; tr[u].add %= mod;
            return ;
        }
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1;
        if (l <= mid) mul(tr[u].ls, lc, mid, l, r, v);
        if (r > mid) mul(tr[u].rs, mid + 1, rc, l, r, v);
        pushup(u);
    }
    long query(int u, int lc, int rc, int l, int r) {
        if (l <= lc && rc <= r) return tr[u].val;
        pushdown(u, rc - lc + 1);
        int mid = lc + rc >> 1;
        long ans = 0;
        if (l <= mid) ans = query(tr[u].ls, lc, mid, l, r);
        if (r > mid) ans += query(tr[u].rs, mid + 1, rc, l, r);
        return ans;
    }
    void pushdown(int u, int len) {
        if (tr[u] == null) tr[u] = new Node();
        if (tr[u].ls == 0) {
            tr[u].ls = ++loc;
            tr[tr[u].ls] = new Node();
        }
        if (tr[u].rs == 0) {
            tr[u].rs = ++loc;
            tr[tr[u].rs] = new Node();
        }
        long mul = tr[u].mul, add = tr[u].add;
        tr[tr[u].ls].val = tr[tr[u].ls].val * mul + (len / 2) * add; tr[tr[u].rs].val = tr[tr[u].rs].val * mul + (len / 2) * add;
        tr[tr[u].ls].mul *= mul; tr[tr[u].rs].mul *= mul;
        tr[tr[u].ls].add = tr[tr[u].ls].add * mul + add; tr[tr[u].rs].add = tr[tr[u].rs].add * mul + add;
        tr[tr[u].ls].val %= mod; tr[tr[u].rs].val %= mod;
        tr[tr[u].ls].mul %= mod; tr[tr[u].rs].mul %= mod;
        tr[tr[u].ls].add %= mod; tr[tr[u].rs].add %= mod;
        tr[u].add = 0; tr[u].mul = 1;
    }
    void pushup(int u) {
        tr[u].val = tr[tr[u].ls].val + tr[tr[u].rs].val;
        tr[u].val %= mod;
    }
    public void append(int val) {
        cnt++;
        add(1, 1, N, cnt, cnt, val);
    }
    public void addAll(int inc) {
        if (cnt == 0) return ;
        add(1, 1, N, 1, cnt, inc);
    }
    public void multAll(int m) {
        if (cnt == 0) return ;
        mul(1, 1, N, 1, cnt, m);
    }
    public int getIndex(int idx) {
        return idx + 1 > cnt ? -1 : (int)(query(1, 1, N, idx + 1, idx + 1) % mod);
    }
}

  • 时间复杂度：查询次数为 $m$，值域大小为 $n$，插入和查询复杂度均为 $O(\log{n})$
  • 空间复杂度：$O(m * \log{n})$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1622 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。