#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 2e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, q;
ll pw[MAXN][3], dp[3][MAXN][3];
string s;
struct node{
ll ans = 0, bit1 = 0, bas3 = 0;
bool ok = 0;
} t[2*MAXN];
void build(int v, int l, int r){
if(l == r){
t[v].ans = s[l] - '0';
if(t[v].ans >= 4){
t[v].bit1 = 1;
t[v].bas3 = 1;
}else if(t[v].ans > 1){
t[v].bit1 = 1;
}
t[v].ok = 1;
}else{
int m = (l + r) / 2;
build(2*v, l, m);
build(2*v + 1, m + 1, r);
int l2 = r - m;
t[v].ans = 0;
t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod;
t[v].ans = (t[v].ans - (t[2*v].bit1*pw[l2][2]%mod) + mod)%mod;
t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod;
t[v].ans = (t[v].ans - (t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod) + mod)%mod;
if(s[l] == '3'){
t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod;
while(t[v].bas3 < 0) t[v].bas3 += mod;
}else if(s[l] >= '4'){
t[v].bas3 = pw[r - l][0];
}else{
t[v].bas3 = 0;
}
t[v].bit1 = 0;
t[v].bit1 = (t[v].bit1 + t[2*v].ans*pw[l2 - 1][0]%mod)%mod;
t[v].bit1 = (t[v].bit1 - t[2*v].bit1*pw[l2 - 1][2]%mod + mod)%mod;
if(s[m] == '1'){
t[v].bit1 += t[2*v].ok*(dp[0][l2][1] + dp[1][l2][1])%mod;
t[v].bit1 %= mod;
}else{
t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod;
t[v].bit1 %= mod;
}
if(s[m] == '1' && s[m + 1] == '3'){
t[v].ok = 0;
}else{
t[v].ok = (t[2*v].ok && t[2*v + 1].ok);
}
}
}
void upd(int v, int l, int r, int pos, char val){
if(l == r){
s[l] = val;
t[v].ans = s[l] - '0';
if(t[v].ans >= 4){
t[v].bit1 = 1;
t[v].bas3 = 1;
}else if(t[v].ans > 1){
t[v].bit1 = 1;
}
t[v].ok = 1;
}else{
int m = (l + r) / 2;
if(pos <= m) upd(2*v, l, m, pos, val);
else upd(2*v + 1, m + 1, r, pos, val);
int l2 = r - m;
t[v].ans = 0;
t[v].ans = (t[v].ans + t[2*v].ans*pw[l2][0]%mod)%mod;
t[v].ans = (t[v].ans - t[2*v].bit1*pw[l2][2]%mod + mod)%mod;
t[v].ans = (t[v].ans + t[2*v].ok*t[2*v + 1].ans%mod)%mod;
t[v].ans = (t[v].ans - t[2*v].ok*(s[m] == '1')*t[2*v + 1].bas3%mod + mod)%mod;
if(s[l] == '3'){
t[v].bas3 = (t[v].ans - 2*pw[r - l][0]%mod - pw[r - l + 1][1] + 2*mod)%mod;
while(t[v].bas3 < 0) t[v].bas3 += mod;
}else if(s[l] >= '4'){
t[v].bas3 = pw[r - l][0];
}else{
t[v].bas3 = 0;
}
t[v].bit1 = 0;
t[v].bit1 = (t[v].bit1 + t[2*v].ans*pw[l2 - 1][0]%mod)%mod;
t[v].bit1 = (t[v].bit1 - t[2*v].bit1*pw[l2 - 1][2]%mod + mod)%mod;
if(s[m] == '1'){
t[v].bit1 += t[2*v].ok*(dp[0][l2][1] + dp[1][l2][1])%mod;
t[v].bit1 %= mod;
}else{
t[v].bit1 += t[2*v].ok*t[2*v + 1].bit1%mod;
t[v].bit1 %= mod;
}
if(s[m] == '1' && s[m + 1] == '3'){
t[v].ok = 0;
}else{
t[v].ok = (t[2*v].ok && t[2*v + 1].ok);
}
}
}
node que(int v, int tl, int tr, int l, int r){
if(l > r){
node a = {-1, -1, -1, 0};
return a;
}else if(l == tl && r == tr){
return t[v];
}else{
int tm = (tl + tr) / 2;
node left = que(2*v, tl, tm, l, min(tm, r)),
right = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
if(r <= tm){
return left;
}else if(l >= tm + 1){
return right;
}else{
node res;
int l2 = r - tm;
res.ans = (res.ans + left.ans*pw[l2][0]%mod)%mod;
res.ans = (res.ans - left.bit1*pw[l2][2]%mod + mod)%mod;
res.ans = (res.ans + left.ok*right.ans%mod)%mod;
res.ans = (res.ans - left.ok*(s[tm] == '1')*right.bas3%mod + mod)%mod;
if(s[l] == '3'){
res.bas3 = (res.ans - (2*pw[r - l][0]%mod) - pw[r - l + 1][1] + 2*mod)%mod;
while(res.bas3 < 0) res.bas3 += mod;
}else if(s[l] >= '4'){
res.bas3 = pw[r - l][0];
}else{
res.bas3 = 0;
}
res.bit1 = 0;
res.bit1 = (res.bit1 + (left.ans*pw[l2 - 1][0]%mod))%mod;
res.bit1 = (res.bit1 - (left.bit1*pw[l2 - 1][2]%mod) + mod)%mod;
if(s[tm] == '1'){
res.bit1 += left.ok*(dp[0][l2][1] + dp[1][l2][1])%mod;
res.bit1 %= mod;
}else{
res.bit1 += left.ok*right.bit1%mod;
res.bit1 %= mod;
}
if(s[tm] == '1' && s[tm + 1] == '3'){
res.ok = 0;
}else{
res.ok = (left.ok && right.ok);
}
return res;
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
#ifdef Local
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
#endif
cin>>n>>q;
pw[0][0] = 1;
dp[0][1][0] = 8;
dp[0][1][1] = 1;
dp[0][1][2] = 1;
pw[1][0] = 10;
for(int i = 2; i < MAXN ; i++){
dp[0][i][0] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])*8 % mod;
dp[0][i][1] = (dp[0][i - 1][0] + dp[0][i - 1][1] + dp[0][i - 1][2])%mod;
dp[0][i][2] = (dp[0][i - 1][0] + dp[0][i - 1][2])%mod;
pw[i][0] = (dp[0][i][0] + dp[0][i][1] + dp[0][i][2])%mod;
}
pw[0][1] = 0;
dp[1][1][1] = 1;
pw[1][1] = 1;
for(int i = 2; i < MAXN ; i++){
dp[1][i][0] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])*8 % mod;
dp[1][i][1] = (dp[1][i - 1][0] + dp[1][i - 1][1] + dp[1][i - 1][2])%mod;
dp[1][i][2] = (dp[1][i - 1][0] + dp[1][i - 1][2])%mod;
pw[i][1] = (dp[1][i][0] + dp[1][i][1] + dp[1][i][2])%mod;
}
pw[0][2] = 0;
dp[2][1][2] = 1;
pw[1][2] = 1;
for(int i = 2; i < MAXN ; i++){
dp[2][i][0] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod*8% mod;
dp[2][i][1] = (dp[2][i - 1][0] + dp[2][i - 1][1] + dp[2][i - 1][2])%mod;
dp[2][i][2] = (dp[2][i - 1][0] + dp[2][i - 1][2])%mod;
pw[i][2] = (dp[2][i][0] + dp[2][i][1] + dp[2][i][2])%mod;
}
cin>>s;
build(1, 0, n - 1);
node cr = que(1, 0, n - 1, 0, n - 1);
cout<<(cr.ans + cr.ok)%mod<<endl;
while(q--){
int type;
cin>>type;
if(type == 1){
int l, r;
cin>>l>>r;
node cr = que(1, 0, n - 1, l-1, r-1);
cout<<(cr.ans + cr.ok)%mod<<endl;
}else{
int idx;
char val;
cin>>idx>>val;
idx--;
upd(1, 0, n - 1, idx, val);
}
}
#ifdef Local
cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
#endif
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
19712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
19712 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
