//#pragma GCC optimize("Ofast,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
#define int long long
const int maxn = 2e5+5;
const int mod = 1e9+7;
int n, q;
string s;
int p[maxn];
void prec(){
p[0] = 1, p[1] = 10;
for(int i = 2; i < maxn; ++i){
p[i] = (p[i - 1] * 10 - p[i - 2] + mod * mod) % mod;
}
}
struct Node{
int val, ft, lt, both;
int sz, check;
int ft_pos, lt_pos;
friend Node operator + (const Node &a, const Node &b){
if(a.sz == 0) return b;
if(b.sz == 0) return a;
Node res;
res.sz = a.sz + b.sz;
res.ft_pos = a.ft_pos, res.lt_pos = b.lt_pos;
if(a.lt_pos == 1 and b.ft_pos == 3) res.check = 0;
else res.check = (a.check & b.check);
bool gud = (a.check and a.ft_pos == 3);
bool nice = (a.check and a.lt_pos == 1);
res.val = (a.val - a.check) * p[b.sz] + (a.check ? b.val : 0);
res.ft = (a.ft - gud) * p[b.sz] + (gud ? b.val : 0);
res.lt = (a.val - a.check) * p[b.sz - 1] + (a.check ? b.lt : 0);
res.both = (a.ft - gud) * p[b.sz - 1] + (gud ? b.lt : 0);
res.val -= ((a.lt - nice) * p[b.sz - 1] + (nice ? b.ft : 0));
res.ft -= ((a.both - (gud and nice)) * p[b.sz - 1] + (gud and nice ? b.ft : 0));
if(b.sz >= 2) res.lt -= ((a.lt - nice) * p[b.sz - 2] + (nice ? b.both : 0));
if(b.sz >= 2) res.both -= ((a.both - (gud and nice)) * p[b.sz - 2] + (gud and nice ? b.both : 0));
res.val = (res.val + mod * mod) % mod;
res.ft = (res.ft + mod * mod) % mod;
res.lt = (res.lt + mod * mod) % mod;
res.both = (res.both + mod * mod) % mod;
// debug(res.sz, res.ft_pos, res.lt_pos, res.val, res.ft, res.lt);
return res;
}
};
Node emp = {0, 0, 0, 0, 0, 0, 0, 0};
struct SegTree{
int n;
vector<Node> tree;
void init(int sz){
n = sz;
tree.resize(n * 4 + 6, emp);
}
void build(int ind, int l, int r){
if(l == r){
int c = s[l] - '0' + 1;
tree[ind] = Node({c, (c > 3), (c > 1), 0, 1, 1, c - 1, c - 1});
return;
}
int mid = (l + r) / 2;
build(ind * 2, l, mid);
build(ind * 2 + 1, mid + 1, r);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
// debug(ind, l, r, tree[ind].val);
}
void update(int ind, int l, int r, int pos, int val){
if(l == r){
++val;
tree[ind] = Node({val, (val > 3), (val > 1), 0, 1, 1, val - 1, val - 1});
return;
}
int mid = (l + r) / 2;
if(l <= pos and pos <= mid) update(ind * 2, l, mid, pos, val);
else update(ind * 2 + 1, mid + 1, r, pos, val);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
}
Node get(int ind, int l, int r, int x, int y){
if(l > y || r < x) return emp;
if(x <= l and r <= y) return tree[ind];
int mid = (l + r) / 2;
return get(ind * 2, l, mid, x, y) + get(ind * 2 + 1, mid + 1, r, x, y);
}
void update(int pos, int val){
update(1, 1, n, pos, val);
}
Node get(int x, int y){
return get(1, 1, n, x, y);
}
} st;
void solve(){
prec();
// debug(p[0], p[1], p[2], p[3]);
cin >> n >> q;
cin >> s;
s = ' ' + s;
st.init(n);
st.build(1, 1, n);
// debug(st.get(1, 2).val_tight, st.get(1, 1).val_tight);
for(int i = 1; i <= q; ++i){
int op, l, r; cin >> op >> l >> r;
if(op == 1){
cout << st.get(l, r).val << '\n';
}
else{
st.update(l, r);
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int test = 1;
// cin >> test;
for(int i = 1; i <= test; i++){
// cout << "Case " << "#" << i << ": ";
solve();
}
cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
4176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
