Submission #272481

#TimeUsernameProblemLanguageResultExecution timeMemory
272481Atill83Lucky Numbers (RMI19_lucky)C++14
0 / 100
29 ms19712 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...