#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define int long long
using namespace std;
typedef pair<int,int> ii;
///1 is tail (one)
///3 is head (three)
int mod = 1000000007;
void fix(int &x){
x %= mod;
if(x < 0) x += mod;
}
int arr[100005];
int ten[100005];
struct data{
int cnt = 0;
int cnttail = 0;
int cnthead = 0;
int cntboth = 0;
int len = 1;
bool isHead = false;
bool isTail = false;
bool isOk = true;
};
void out(data D){
cout << "ways : " << D.cnt << "\n";
cout << "waysHead : " << D.cnthead << "\n";
cout << "waysTail : " << D.cnttail << "\n";
cout << "waysBoth : " << D.cntboth << "\n";
cout << "len : " << D.len << "\n\n";
}
data basic(int x){
data val;
val.cnt = x;
if(x > 1){
val.cnttail = 1;
}
if(x > 3){
val.cnthead = 1;
}
if(x == 1) val.isTail = true;
if(x == 3) val.isHead = true;
return val;
}
int B[11];
int ALL[100005];
int ONE[100005];
inline int ways(int digits){
if(digits == 0) return 1;
return ALL[digits-1];
}
data merge(data l, data r){
data val;
///consider when l is not bounded
val.cnt = l.cnt * ways(r.len);
fix(val.cnt);
val.cnt -= l.cnttail * ways(r.len-1);
fix(val.cnt);
val.cnttail = l.cnt * ways(r.len-1);
fix(val.cnttail);
if(r.len >= 2) val.cnttail -= l.cnttail * ways(r.len-2);
fix(val.cnttail);
val.cnthead = l.cnthead * ways(r.len);
fix(val.cnthead);
val.cnthead -= l.cntboth * ways(r.len-1);
fix(val.cnthead);
val.cntboth = l.cnthead * ways(r.len-1);
fix(val.cntboth);
if(r.len >= 2) val.cntboth -= l.cntboth * ways(r.len-2);
fix(val.cntboth);
///when l is bounded
if(l.isOk){
if(l.isHead){
val.cnthead += r.cnthead;
if(l.isTail) val.cnthead -= r.cnthead;
fix(val.cnthead);
val.cntboth += r.cntboth;
if(l.isTail) val.cntboth -= r.cntboth;
fix(val.cntboth);
}
val.cnt += r.cnt;
if(l.isTail) val.cnt -= r.cnthead;
fix(val.cnt);
val.cnttail += r.cnttail;
if(l.isTail) val.cnttail -= r.cntboth;
fix(val.cnttail);
}
val.len = l.len + r.len;
val.isHead = l.isHead;
val.isTail = r.isTail;
val.isOk = (l.isOk && r.isOk);
if(l.isTail && r.isHead) val.isOk = false;
val.cnt %= mod;
val.cnttail %= mod;
val.cnthead %= mod;
val.cntboth %= mod;
return val;
}
struct node{
int s, e, m;
data val;
node *l, *r;
node(int S, int E){
s = S, e = E; m =(s+e)/2;
if(s == e){
val = basic(arr[s]);
//cout << s << " " << e << ":\n";
//out(val);
}
else{
l = new node(s,m);
r = new node(m+1,e);
val = merge(l->val, r->val);
//cout << s << " " << e << ":\n";
//out(val);
}
}
void update(int P, int x){
if(s == e){
val = basic(x);
//out(val);
return;
}
if(P <= m) l->update(P,x);
else r->update(P,x);
val = merge(l->val, r->val);
}
data query(int S, int E){
if(s == S && e == E) return val;
else if(E <= m) return l->query(S,E);
else if(S >= m+1) return r->query(S,E);
else return merge(l->query(S,m), r->query(m+1,E));
}
} *root;
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n, Q; cin >> n >> Q;
string s; cin >> s;
for(int i = 0;i < n;i++){
arr[i] = (s[i] - '0');
}
ALL[0] = 10;
ONE[0] = 1;
for(int i = 1;i <= 100003;i++){
ONE[i] = ALL[i-1];
ALL[i] = ALL[i-1] * 10 - ONE[i-1];
ALL[i] %= mod;
fix(ALL[i]);
}
root = new node(0,n-1);
data D = root->val;
int ans = D.cnt;
if(D.isOk) ans++;
fix(ans);
cout << ans << '\n';
while(Q--){
int type = 0;
cin >> type;
if(type == 1){
int l, r; cin >> l >> r;
l--, r--;
/*
data D = root->query(l,r);
int ans = D.cnt;
if(D.isOk) ans++;
fix(ans);
cout << ans << "\n";
*/
data D = basic(arr[l]);
for(int i = l+1;i <= r;i++){
D = merge(D, basic(arr[i]));
}
int ans = D.cnt;
if(D.isOk) ans++;
fix(ans);
cout << ans << "\n";
}
else{
int i, x; cin >> i >> x;
arr[i-1] = x;
root->update(i-1,x);
}
}
//cout << "\n" << ways(2);
}
/*
*
def chk(x):
ans = 0;
for i in range(x):
s = str(i)
for j in range(len(s)-1):
if s[j] == '1' and s[j+1] == '3':
ans+=1
break
return x - ans
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1920 KB |
Integer 949243848 violates the range [-1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1920 KB |
Integer 949243848 violates the range [-1, 1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
