题意
初始有 $n$ 个空串，进行 $q$ 次操作
- 把 $[l,\ r]$ 中每个字符串首尾都加上 $d$ 。
- 查询 $\displaystyle \sum_{i=l}^rs_i$
题解
对 $s_i$ 执行操作 $1$
\[\large s_i = [d * 10^{len(s_i)} + s_i] * 10 + d\]设
$sum(l, r)$ 表示 $\displaystyle \sum_{i=l}^rs_i$ ，
$len(s_i)$ 表示 $s_i$ 的长度，
$pow(l, r)$ 表示 $\displaystyle \sum_{i=l}^r10^{len(s_i)}$ ，
对区间 $[l,\ r]$ 执行操作 $1$
\[\large sum(l, r) = [d * pow(l, r) + sum(l, r)] * 10 + d * (r - l + 1)\\ \large pow(l, r) = \sum_{i=l}^r10^{len(s_i) + 2} = 10^2\sum_{i=l}^r10^{len(s_i)} = 10^2 * pow(l, r)\]对区间 $[l,\ r]$ 执行两次操作 $1$
\[\begin{aligned} sum(l, r) &= [(d_2 * 10 + d_1) * pow(l, r) + sum(l, r)] * 10^2 \\ &+ (d_1 * 10 + d_2) * (r - l + 1)\\ pow(l, r) &= 10^4 * pow(l, r) \end{aligned}\]对区间 $[l, r]$ 执行 $k$ 次操作 $1$
\[\begin{aligned} sum(l, r) &= [(d_k * 10^{k-1} + d_{k-1} * 10^{k-2} + ...+ d_1) * pow(l, r) + sum(l, r)] * 10 ^ k\\ &+ (d_1*10^{k-1} + d_2*10^{k-2}+...+d_k) * (r - l + 1)\\ pow(l, r) &= 10^{2k} * pow(l, r) \end{aligned}\]因此，
对于 $pow(s_i)$ 和 $sum(l, r)$ 是需要更新的量，
而
$(d_k * 10^{k-1} + d_{k-1} * 10^{k-2} + …+ d_1)$ 、 $(d_1 * 10^{k-1} + d_{2} * 10^{k-2}+…+d_k)$
和
$10^k$ 、 $10^{2k}$
是懒惰标记需要记录的量，
如何更新懒惰标记：
设
$lazy_1 = (d_k * 10^{k-1} + d_{k-1} * 10^{k-2} + …+ d_1)$ ，
$lazy_2 = (d_1 * 10^{k-1} + d_2 * 10^{k-2}+…+d_k)$ ，
注意到 $d$ 为 $1$ 位数，因此 $lazy_1$ 和 $lazy_2$ 是 $k$ 位数，
当 $newlazy_1$ 要更新给 $lazy_1$ 时：
\[lazy_1 = newlazy_1 * 10 ^ k + lazy_1\]同理：
\[lazy_2 = lazy2 * 10 ^ {newk} + newlazy_2\]且
\[k = k + newk\]因此，共有上述三个懒惰标记。
代码
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
96
97
98
const int MOD = 1e9+7;
const int N = 1e5+7;
// ------- 变量 ------- //
int n, m;
// ------- 函数 ------- //
inline int add(int a, int b) { return (a += b) >= MOD ? a - MOD : a; }
inline int mul(int a, int b) { return 1ll * a * b % MOD; }
inline int qpow(ll a, ll b) {
int r = 1;
for (a %= MOD; b; a = a * a % MOD, b >>= 1)
if (b & 1) r = 1ll * r * a % MOD;
return r;
}
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, m, ls
#define rson m + 1, r, rs
struct node { int sz, sum, pow, lazy1, lazy2, k; } t[N<<2];
inline void Add(int rt, int newlazy1, int newlazy2, int newk) {
t[rt].lazy1 = add(t[rt].lazy1, mul(newlazy1, qpow(10, t[rt].k)));
t[rt].lazy2 = add(mul(t[rt].lazy2, qpow(10, newk)), newlazy2);
t[rt].k = add(t[rt].k, newk);
t[rt].sum = add
(
mul
(
add
(
mul(newlazy1, t[rt].pow),
t[rt].sum
),
qpow(10, newk)
),
mul(newlazy2, t[rt].sz)
);
t[rt].pow = mul(qpow(10, mul(2, newk)), t[rt].pow);
}
inline void PushDown(int rt) {
if (t[rt].k) {
Add(ls, t[rt].lazy1, t[rt].lazy2, t[rt].k);
Add(rs, t[rt].lazy1, t[rt].lazy2, t[rt].k);
t[rt].lazy1 = t[rt].lazy2 = t[rt].k = 0;
}
}
inline void build(int l, int r, int rt) {
t[rt].lazy1 = t[rt].lazy2 = t[rt].k = 0; t[rt].sz = r - l + 1;
if (l == r) { t[rt].sum = 0; t[rt].pow = 1; return; }
int m = (l + r) >> 1;
build(lson); build(rson);
t[rt].sum = add(t[ls].sum, t[rs].sum);
t[rt].pow = add(t[ls].pow, t[rs].pow);
}
inline void upd(int L, int R, int val, int l, int r, int rt) {
if (L <= l && r <= R) { Add(rt, val, val, 1); return ; }
PushDown(rt);
int m = (l + r) >> 1;
if (L <= m) upd(L, R, val, lson);
if (m < R) upd(L, R, val, rson);
t[rt].sum = add(t[ls].sum, t[rs].sum);
t[rt].pow = add(t[ls].pow, t[rs].pow);
}
inline int qry(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return t[rt].sum;
PushDown(rt);
int m = (l + r) >> 1;
int res = 0;
if (L <= m) res = add(res, qry(L, R, lson));
if (m < R) res = add(res, qry(L, R, rson));
return res;
}
void Init() {
scanf("%d%d", &n, &m);
}
int Solve() {
build(1, n, 1);
while (m--) {
char op[10]; scanf("%s", op);
int l, r, d;
if (op[0] == 'w') {
scanf("%d%d%d", &l, &r, &d);
upd(l, r, d, 1, n, 1);
} else {
scanf("%d%d", &l, &r);
printf("%d\n", qry(l, r, 1, n, 1));
}
}
return 0;
}
