请你实现三个 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 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fancy-sequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
import java.util.Arrays;
class Fancy {
private SegmentTree segmentTree;
public Fancy() {
this.segmentTree = new SegmentTree(100000);
}
public void append(int val) {
segmentTree.append(val);
}
public void addAll(int inc) {
segmentTree.addAll(inc);
}
public void multAll(int m) {
segmentTree.multAll(m);
}
public int getIndex(int idx) {
return segmentTree.getIndex(idx);
}
public static void main(String[] args) {
Fancy fancy = new Fancy();
fancy.addAll(1); // 奇妙序列:[2+3] -> [5]
fancy.getIndex(0); // 返回 26
}
}
class SegmentTree {
private static final int MOD = 1000000007;
private int limit;
private long[] sum;
private long[] add;
private long[] multiply;
private int size;
public SegmentTree(int limit) {
this.limit = limit;
this.sum = new long[limit << 2 | 1];
this.add = new long[limit << 2 | 1];
this.multiply = new long[limit << 2 | 1];
Arrays.fill(multiply, 1);
}
private void pushUp(int rt) {
this.sum[rt] = (this.sum[rt << 1] + this.sum[rt << 1 | 1]) % MOD;
}
private void pushDown(int rt, int ln, int rn) {
if (add[rt] != 0 || multiply[rt] != 1) {
sum[rt << 1] = (sum[rt << 1] * multiply[rt] + ln * add[rt]) % MOD;
sum[rt << 1 | 1] = (sum[rt << 1 | 1] * multiply[rt] + rn * add[rt]) % MOD;
multiply[rt << 1] = multiply[rt << 1] * multiply[rt] % MOD;
multiply[rt << 1 | 1] = multiply[rt << 1 | 1] * multiply[rt] % MOD;
add[rt << 1] = (add[rt << 1] * multiply[rt] + add[rt]) % MOD;
add[rt << 1 | 1] = (add[rt << 1 | 1] * multiply[rt] + add[rt]) % MOD;
multiply[rt] = 1;
add[rt] = 0;
}
}
private void multiply(int L, int R, int l, int r, int rt, int x) {
if (L <= l && r <= R) {
sum[rt] = sum[rt] * x % MOD;
multiply[rt] = multiply[rt] * x % MOD;
add[rt] = add[rt] * x % MOD;
return;
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
multiply(L, R, l, mid, rt << 1, x);
}
if (mid < R) {
multiply(L, R, mid + 1, r, rt << 1 | 1, x);
}
pushUp(rt);
}
private void add(int L, int R, int l, int r, int rt, int x) {
if (L <= l && r <= R) {
sum[rt] = (sum[rt] + (long) (r - l + 1) * x) % MOD;
add[rt] = (add[rt] + x) % MOD;
return;
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
add(L, R, l, mid, rt << 1, x);
}
if (mid < R) {
add(L, R, mid + 1, r, rt << 1 | 1, x);
}
pushUp(rt);
}
private long query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
long ans = 0;
if (L <= mid) {
ans = (ans + query(L, R, l, mid, rt << 1)) % MOD;
}
if (mid < R) {
ans = (ans + query(L, R, mid + 1, r, rt << 1 | 1)) % MOD;
}
return ans;
}
public void append(int x) {
this.size++;
add(this.size, this.size, 1, limit, 1, x);
}
public void addAll(int x) {
if (size == 0) {
return;
}
add(1, this.size, 1, limit, 1, x);
}
public void multAll(int x) {
if (size == 0) {
return;
}
multiply(1, this.size, 1, limit, 1, x);
}
public int getIndex(int index) {
if (index >= size) {
return -1;
}
return (int) query(index + 1, index + 1, 1, limit, 1);
}
}
/**
* Your Fancy object will be instantiated and called as such:
* Fancy obj = new Fancy();
* obj.append(val);
* obj.addAll(inc);
* obj.multAll(m);
* int param_4 = obj.getIndex(idx);
*/