class Solution {
static final int MOD = 1_000_000_007;
class Node {
long val;
int len;
long sum;
Node() {}
Node(long v, int l, long s) {
val = v;
len = l;
sum = s;
}
}
Node[] tree;
long[] pow10;
char[] arr;
public int[] sumAndMultiply(String s, int[][] queries) {
int n = s.length();
arr = s.toCharArray();
pow10 = new long[n + 1];
pow10[0] = 1;
for (int i = 1; i <= n; i++) {
pow10[i] = (pow10[i - 1] * 10) % MOD;
}
tree = new Node[4 * n];
build(1, 0, n - 1);
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
Node res = query(1, 0, n - 1, queries[i][0], queries[i][1]);
ans[i] = (int) ((res.val * (res.sum % MOD)) % MOD);
}
return ans;
}
private void build(int idx, int l, int r) {
if (l == r) {
int d = arr[l] - '0';
if (d == 0) {
tree[idx] = new Node(0, 0, 0);
} else {
tree[idx] = new Node(d, 1, d);
}
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
tree[idx] = merge(tree[idx << 1], tree[idx << 1 | 1]);
}
private Node query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[idx];
int mid = (l + r) >> 1;
if (qr <= mid) return query(idx << 1, l, mid, ql, qr);
if (ql > mid) return query(idx << 1 | 1, mid + 1, r, ql, qr);
Node left = query(idx << 1, l, mid, ql, qr);
Node right = query(idx << 1 | 1, mid + 1, r, ql, qr);
return merge(left, right);
}
private Node merge(Node a, Node b) {
Node res = new Node();
res.len = a.len + b.len;
res.sum = a.sum + b.sum;
res.val = (a.val * pow10[b.len] + b.val) % MOD;
return res;
}
}
class Node:
def __init__(self, val=0, length=0, sm=0):
self.val = val
self.len = length
self.sum = sm
class Solution:
MOD = 1_000_000_007
def sumAndMultiply(self, s: str, queries: List[List[int]]) -> List[int]:
n = len(s)
self.arr = list(s)
self.pow10 = [1] * (n + 1)
for i in range(1, n + 1):
self.pow10[i] = (self.pow10[i - 1] * 10) % self.MOD
self.tree = [Node() for _ in range(4 * n)]
self.build(1, 0, n - 1)
ans = []
for l, r in queries:
res = self.query(1, 0, n - 1, l, r)
ans.append((res.val * (res.sum % self.MOD)) % self.MOD)
return ans
def build(self, idx, l, r):
if l == r:
d = int(self.arr[l])
if d == 0:
self.tree[idx] = Node(0, 0, 0)
else:
self.tree[idx] = Node(d, 1, d)
return
mid = (l + r) // 2
self.build(idx * 2, l, mid)
self.build(idx * 2 + 1, mid + 1, r)
self.tree[idx] = self.merge(self.tree[idx * 2], self.tree[idx * 2 + 1])
def query(self, idx, l, r, ql, qr):
if ql <= l and r <= qr:
return self.tree[idx]
mid = (l + r) // 2
if qr <= mid:
return self.query(idx * 2, l, mid, ql, qr)
if ql > mid:
return self.query(idx * 2 + 1, mid + 1, r, ql, qr)
left = self.query(idx * 2, l, mid, ql, qr)
right = self.query(idx * 2 + 1, mid + 1, r, ql, qr)
return self.merge(left, right)
def merge(self, a, b):
res = Node()
res.len = a.len + b.len
res.sum = a.sum + b.sum
res.val = (a.val * self.pow10[b.len] + b.val) % self.MOD
return res
class Solution {
static const int MOD = 1000000007;
struct Node {
long long val = 0;
int len = 0;
long long sum = 0;
};
vector<Node> tree;
vector<long long> pow10;
string arr;
public:
vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
arr = s;
int n = s.size();
pow10.assign(n + 1, 1);
for (int i = 1; i <= n; i++)
pow10[i] = (pow10[i - 1] * 10) % MOD;
tree.assign(4 * n, Node());
build(1, 0, n - 1);
vector<int> ans;
for (auto &q : queries) {
Node res = query(1, 0, n - 1, q[0], q[1]);
ans.push_back((res.val * (res.sum % MOD)) % MOD);
}
return ans;
}
void build(int idx, int l, int r) {
if (l == r) {
int d = arr[l] - '0';
if (d == 0)
tree[idx] = {0, 0, 0};
else
tree[idx] = {d, 1, d};
return;
}
int mid = (l + r) / 2;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}
Node query(int idx, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return tree[idx];
int mid = (l + r) / 2;
if (qr <= mid)
return query(idx * 2, l, mid, ql, qr);
if (ql > mid)
return query(idx * 2 + 1, mid + 1, r, ql, qr);
Node left = query(idx * 2, l, mid, ql, qr);
Node right = query(idx * 2 + 1, mid + 1, r, ql, qr);
return merge(left, right);
}
Node merge(Node a, Node b) {
Node res;
res.len = a.len + b.len;
res.sum = a.sum + b.sum;
res.val = (a.val * pow10[b.len] + b.val) % MOD;
return res;
}
};
var sumAndMultiply = function(s, queries) {
const MOD = 1000000007n;
const n = s.length;
const pow10 = new Array(n + 1).fill(0n);
pow10[0] = 1n;
for (let i = 1; i <= n; i++) {
pow10[i] = (pow10[i - 1] * 10n) % MOD;
}
class Node {
constructor(val = 0n, len = 0, sum = 0n) {
this.val = val;
this.len = len;
this.sum = sum;
}
}
const tree = new Array(4 * n);
function merge(a, b) {
return new Node(
(a.val * pow10[b.len] + b.val) % MOD,
a.len + b.len,
a.sum + b.sum
);
}
function build(idx, l, r) {
if (l === r) {
const d = Number(s[l]);
if (d === 0)
tree[idx] = new Node(0n, 0, 0n);
else
tree[idx] = new Node(BigInt(d), 1, BigInt(d));
return;
}
const mid = (l + r) >> 1;
build(idx * 2, l, mid);
build(idx * 2 + 1, mid + 1, r);
tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
}
function query(idx, l, r, ql, qr) {
if (ql <= l && r <= qr) return tree[idx];
const mid = (l + r) >> 1;
if (qr <= mid)
return query(idx * 2, l, mid, ql, qr);
if (ql > mid)
return query(idx * 2 + 1, mid + 1, r, ql, qr);
return merge(
query(idx * 2, l, mid, ql, qr),
query(idx * 2 + 1, mid + 1, r, ql, qr)
);
}
build(1, 0, n - 1);
const ans = [];
for (const [l, r] of queries) {
const res = query(1, 0, n - 1, l, r);
ans.push(Number((res.val * (res.sum % MOD)) % MOD));
}
return ans;
};