1622. 奇妙序列Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

请实现 Fancy 类：

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

示例：

输入：
["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 <= 105
总共最多会有 105 次对 append，addAll，multAll 和 getIndex 的调用。

# 思路

线段树

# 解法


class Fancy {
    private static final int mod = (int) 1e9 + 7;
    private static final int maxNode = (int) 1e5 + 1;
    
    private class TreeNode {
        public TreeNode left = null;
        public TreeNode right = null;
        public long data = 0;
        public long addend = 0;
        public long times = 1;
        public boolean lazy = false;
    }
    
    private int size = 0;
    private TreeNode tree = null;
    
    private void update(TreeNode root, int start, int end, int left, int right, int data, boolean isAdd) {
        if (right < start || end < left)
            return;
        if (left <= start && end <= right) {
            if (isAdd) {
                root.data = (root.data + data) % mod;
                root.addend = (root.addend + data) % mod;
            }
            else {
                root.data = (root.data * data) % mod;
                root.times = (root.times * data) % mod;
                root.addend = (root.addend * data) % mod;
            }
            root.lazy = true;
            return;
        }
        pushDown(root);
        int mid = start + (end - start) / 2;
        if (left <= mid)
            update(root.left, start, mid, left, right, data, isAdd);
        if (mid < right)
            update(root.right, mid + 1, end, left, right, data, isAdd);
    }
    
    private int query(TreeNode root, int start, int end, int index) {
        if (start == end)
            return (int) root.data % mod;
        pushDown(root);
        int mid = start + (end - start) / 2;
        if (index <= mid)
            return query(root.left, start, mid, index);
        else
            return query(root.right, mid + 1, end, index);
    }

    private void pushDown(TreeNode root) {
        if (root.left == null)
            root.left = new TreeNode();
        if (root.right == null)
            root.right = new TreeNode();
        if (root.lazy) {
            root.left.data = (root.left.data * root.times + root.addend) % mod;
            root.left.times = (root.left.times * root.times) % mod;
            root.left.addend = (root.left.addend * root.times + root.addend) % mod;
            root.right.data = (root.right.data * root.times + root.addend) % mod;
            root.right.times = (root.right.times * root.times) % mod;
            root.right.addend = (root.right.addend * root.times + root.addend) % mod;
            root.times = 1;
            root.addend = 0;
            root.left.lazy = true;
            root.right.lazy = true;
            root.lazy = false;
        }
    }
    
    public Fancy() {
        tree = new TreeNode();
    }
    
    public void append(int val) {
        size++;
        update(tree, 1, maxNode, size, size, val, true);
    }
    
    public void addAll(int inc) {
        update(tree, 1, maxNode, 1, size, inc, true);
    }
    
    public void multAll(int m) {
        update(tree, 1, maxNode, 1, size, m, false);
    }
    
    public int getIndex(int index) {
        if (index + 1 > size)
            return -1;
        return query(tree, 1, maxNode, index + 1);
    }
}

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
89
90
91
92
93
94
95

# 总结

分析出几种情况，然后分别对各个情况实现

#Java