#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
const int N = 2e5 + 5;
const int K = 1e2 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18 + 7;
#define all(v) (v).begin(), (v).end()
#define pii pair<int, int>
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
int a[N], d[N][4];
// d[i][0/1/2/3] : numbers < 10^i (1 : first digit = 3) (2 : last digit = 1) (3 : both)
struct node{
int sum, prf, suf, bh, eq, l, r, len;
// prf : first digit = 3
// suf : last digit = 1
// bh : both first digit = 3 and last digit = 1
// eq : if s[l, r] lucky
} st[N * 4];
node merge(const node &l, const node &r){
node cur = {0, 0, 0, 0, 0, 0, 0, 0};
// update sum
cur.sum = (cur.sum + l.sum * d[r.len][0] - l.suf * d[r.len][1] + mod * mod) % mod;
cur.sum = (cur.sum + l.eq * r.sum - (l.eq * a[l.r] == 1) * r.prf + mod * mod) % mod;
// cout << l.sum << ' ' << r.sum << ' ' << cur.sum << '\n';
// update prf
cur.prf = (cur.prf + l.prf * d[r.len][0] - l.bh * d[r.len][1] + mod * mod) % mod;
cur.prf = (cur.prf + (l.eq && a[l.l] == 3) * r.sum - (l.eq && a[l.l] == 3 && a[l.r] == 1) * r.prf + mod * mod) % mod;
// update suf
cur.suf = (cur.suf + l.sum * d[r.len][2] - (l.sum * d[r.len][3]) + mod * mod) % mod;
cur.suf = (cur.suf + (l.eq * r.suf) - (l.eq && a[l.r] == 1) * r.bh + mod * mod) % mod;
// update bh
cur.bh = (cur.bh + l.prf * d[r.len][2] - l.bh * d[r.len][3] + mod * mod) % mod;
cur.bh = (cur.bh + (l.eq && a[l.l] == 3) * r.suf - (l.eq && a[l.l] == 3 && a[l.r] == 1) * r.bh + mod * mod) % mod;
// update eq
cur.eq = l.eq | r.eq | (!(a[l.r] == 1 && a[r.l] == 3));
// update l
cur.l = l.l;
// update r
cur.r = r.r;
// update len
cur.len = l.len + r.len;
return cur;
}
void build(int id, int l, int r){
if(l == r){
st[id] = {a[l], (a[l] > 3), (a[l] > 1), 0, 1, l, l, 1};
return;
}
int mid = l + r >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = merge(st[id * 2], st[id * 2 + 1]);
}
void update(int id, int l, int r, int pos){
if(l > pos || r < pos) return;
if(l == r){
st[id] = {a[l], (a[l] > 3), (a[l] > 1), 0, 1, l, l, 1};
return;
}
int mid = l + r >> 1;
update(id * 2, l, mid, pos);
update(id * 2 + 1, mid + 1, r, pos);
st[id] = merge(st[id * 2], st[id * 2 + 1]);
}
node get(int id, int l, int r, int u, int v){
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
node cur = {-1, -1, -1, -1, -1, -1, -1, -1};
if(u <= mid) cur = get(id * 2, l, mid, u, v);
if(v > mid){
if(cur.len == -1) cur = get(id * 2 + 1, mid + 1, r, u, v);
else cur = merge(cur, get(id * 2 + 1, mid + 1, r, u, v));
}
return cur;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if(ifstream("file.inp")){
freopen("file.inp", "r", stdin);
freopen("file.out", "w", stdout);
}
cin >> n >> q;
for(int i = 1; i <= n; i++){
char d;
cin >> d;
a[i] = d - '0';
}
d[1][0] = 10, d[1][1] = 1, d[1][2] = 1, d[1][3] = 0;
for(int i = 2; i <= n; i++){
d[i][0] = (d[i - 1][0] * 10 - d[i - 1][1] + mod * mod) % mod;
d[i][1] = d[i - 1][0];
d[i][2] = d[i - 1][0];
d[i][3] = d[i - 1][2];
}
build(1, 1, n);
node fu = get(1, 1, n, 1, n);
cout << (fu.sum + fu.eq) % mod << '\n';
while(q--){
int t, x, y;
cin >> t >> x >> y;
if(t == 1){
node dh = get(1, 1, n, x, y);
cout << (dh.sum + dh.eq) % mod << '\n';
}
else{
a[x] = y;
update(1, 1, n, x);
}
}
return 0;
}
// tuntun
Compilation message
lucky.cpp: In function 'void build(long long int, long long int, long long int)':
lucky.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid = l + r >> 1;
| ~~^~~
lucky.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
lucky.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int mid = l + r >> 1;
| ~~^~~
lucky.cpp: In function 'node get(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = l + r >> 1;
| ~~^~~
lucky.cpp: In function 'int main()':
lucky.cpp:109:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen("file.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:110:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen("file.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4572 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
6748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4572 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4572 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
