This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fast_rmi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5+1;
const int M=1e9+7;
void add(int &a,int b){
a+=b;
if(a>=M)
a-=M;
else if(a<0)
a+=M;
}
int mult(int a,int b){
return 1ll*a*b%M;
}
int sm1[3][3];
int sm2[3][3];
struct node{
int dp[3][3][3];
node(){
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++)
dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
}
}
void clr(){
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++)
dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=0;
}
}
};
node mg(const node &a,const node &b){
node c;
for(int f=0;f<=2;f++){
for(int d=0;d<=2;d++){
sm1[d][f]=sm2[d][f]=0;
for(int j=0;j<=2;j++)
add(sm1[d][f],a.dp[d][j][f]),add(sm2[d][f],b.dp[j][d][f]);
}
}
for(int f=0;f<=2;f++){
for(int s=0;s<=2;s++){
for(int d1=0;d1<=2;d1++){
for(int d2=0;d2<=2;d2++){
int nf=(f!=1?f:s);
add(c.dp[d1][d2][nf],mult(sm1[d1][f],sm2[d2][s]));
add(c.dp[d1][d2][nf],-mult(a.dp[d1][0][f],b.dp[1][d2][s]));
}
}
}
}
return c;
}
int gd(int x){
if(x==1)
return 0;
if(x==3)
return 1;
return 2;
}
node t[4*N];
int a[N];
void build(int v,int tl,int tr){
if(tl==tr){
for(int j=0;j<=9;j++){
int f=(j>a[tl]?2:a[tl]==j);
add(t[v].dp[gd(j)][gd(j)][f],1);
}
}
else{
int tm=(tl+tr)>>1;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=mg(t[2*v],t[2*v+1]);
}
}
void upd(int i,int x,int v,int tl,int tr){
if(tl==tr){
t[v].clr();
a[i]=x;
for(int j=0;j<=9;j++){
int f=(j>a[tl]?2:a[tl]==j);
add(t[v].dp[gd(j)][gd(j)][f],1);
}
return;
}
int tm=(tl+tr)>>1;
if(tm>=i)
upd(i,x,2*v,tl,tm);
else
upd(i,x,2*v+1,tm+1,tr);
t[v]=mg(t[2*v],t[2*v+1]);
}
node ans;
bool is=0;
void get(int l,int r,int v,int tl,int tr){
if(tl>=l&&tr<=r){
if(is)
ans=mg(ans,t[v]);
else
ans=t[v];
is=1;
return;
}
if(tl>r||tr<l)
return;
int tm=(tl+tr)>>1;
get(l,r,2*v,tl,tm);
get(l,r,2*v+1,tm+1,tr);
return;
}
int eval(){
int me=0;
for(int f=0;f<=1;f++){
for(int x=0;x<=2;x++)
for(int y=0;y<=2;y++)
add(me,ans.dp[x][y][f]);
}
return me;
}
signed main(){
fast_rmi;
int n,q;
// n=100'000,q=0;
cin>>n>>q;
for(int i=0;i<n;i++){
char c;
cin>>c;
a[i]=c-'0';
}
build(1,0,n-1);
ans=t[1];
cout<<eval()<<'\n';
while(q--){
int tp;
cin>>tp;
if(tp==1){
is=0;
int l,r;
cin>>l>>r;--l;--r;
get(l,r,1,0,n-1);
cout<<eval()<<'\n';
}
else{
int i,x;
cin>>i>>x;
upd(i-1,x,1,0,n-1);
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |