#include <bits/stdc++.h>
#define DIM 100010
#define MOD 1000000007
using namespace std;
int v[DIM];
int n,q,c,x,y,i,_first;
long long sol0,sol1,sol3;
char ch;
struct segment_tree{
long long s00, s01, s03;
long long s10, s11, s13;
long long s30, s31, s33;
};
segment_tree aint[DIM*4], dp[DIM];
void update_node (int nod, int st, int dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
if (dr - st == 1){
aint[nod].s00 = 1LL*aint[fiu_st].s00 * dp[1].s00 % MOD;
aint[nod].s01 = 1LL*aint[fiu_st].s00 * dp[1].s11 % MOD;
aint[nod].s03 = 1LL*aint[fiu_st].s00 * dp[1].s33 % MOD;
if (v[st] != 1 && v[st] != 3){
aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00) % MOD;
aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s11) % MOD;
aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s33) % MOD;
}
aint[nod].s10 = 1LL * aint[fiu_st].s11 * dp[1].s00 % MOD;
aint[nod].s11 = 1LL * aint[fiu_st].s11 * dp[1].s11 % MOD;
if (v[st] == 1){
aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00) % MOD;
aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s11) % MOD;
}
aint[nod].s13 = 0;
aint[nod].s30 = 1LL*aint[fiu_st].s33 * dp[1].s00 % MOD;
aint[nod].s31 = 1LL*aint[fiu_st].s33 * dp[1].s11 % MOD;
aint[nod].s33 = 1LL*aint[fiu_st].s33 * dp[1].s33 % MOD;
if (v[st] == 3){
aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00) % MOD;
aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s11) % MOD;
aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s33) % MOD;
}
return;
}
int mid = (st+dr)>>1;
int nr = dr-mid;
/// stare 00
int sum = 0;
sum = (sum + dp[nr].s00) % MOD;
sum = (sum + dp[nr].s10) % MOD;
sum = (sum + dp[nr].s30) % MOD;
aint[nod].s00 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
/// la cazul asta nu am voie cu 3
int val = sum - dp[nr].s30;
if (val < 0)
val += MOD;
aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;
/// stare 01
sum = 0;
sum = (sum + dp[nr].s01) % MOD;
sum = (sum + dp[nr].s11) % MOD;
sum = (sum + dp[nr].s31) % MOD;
aint[nod].s01 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
val = sum - dp[nr].s31;
if (val < 0)
val += MOD;
aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;
/// stare 03
sum = 0;
sum = (sum + dp[nr].s03) % MOD;
sum = (sum + dp[nr].s13) % MOD;
sum = (sum + dp[nr].s33) % MOD;
aint[nod].s03 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD;
aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD;
val = sum - dp[nr].s33;
if (val < 0)
val += MOD;
aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s01*val % MOD) % MOD;
/// stare 10
sum = 0;
sum = (sum + dp[nr].s00) % MOD;
sum = (sum + dp[nr].s10) % MOD;
sum = (sum + dp[nr].s30) % MOD;
aint[nod].s10 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
val = sum - dp[nr].s30;
if (val < 0)
val += MOD;
aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;
/// stare 11
sum = 0;
sum = (sum + dp[nr].s01) % MOD;
sum = (sum + dp[nr].s11) % MOD;
sum = (sum + dp[nr].s31) % MOD;
aint[nod].s11 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
val = sum - dp[nr].s31;
if (val < 0)
val += MOD;
aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;
/// stare 13
sum = 0;
sum = (sum + dp[nr].s03) % MOD;
sum = (sum + dp[nr].s13) % MOD;
sum = (sum + dp[nr].s33) % MOD;
aint[nod].s13 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD;
aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD;
val = sum - dp[nr].s33;
if (val < 0)
val += MOD;
aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s11*val%MOD) % MOD;
/// stare 30
sum = 0;
sum = (sum + dp[nr].s00) % MOD;
sum = (sum + dp[nr].s10) % MOD;
sum = (sum + dp[nr].s30) % MOD;
aint[nod].s30 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
val = sum - dp[nr].s30;
if (val < 0)
val += MOD;
aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;
/// stare 31
sum = 0;
sum = (sum + dp[nr].s01) % MOD;
sum = (sum + dp[nr].s11) % MOD;
sum = (sum + dp[nr].s31) % MOD;
aint[nod].s31 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
val = sum - dp[nr].s31;
if (val < 0)
val += MOD;
aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;
/// stare 33
sum = 0;
sum = (sum + dp[nr].s03) % MOD;
sum = (sum + dp[nr].s13) % MOD;
sum = (sum + dp[nr].s33) % MOD;
aint[nod].s33 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD;
aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD;
val = sum - dp[nr].s33;
if (val < 0)
val += MOD;
aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s31*val%MOD) % MOD;
/// acum mai ramane cazul in care pastrez fiul stang integral asa cum e si
/// trebuie sa adaug de la fiul drept pt toate starile
/// singurul caz special e cand am pe mid 1
sum = (aint[fiu_dr].s00 + aint[fiu_dr].s01 + aint[fiu_dr].s03) % MOD;
sum = (sum + aint[fiu_dr].s10 + aint[fiu_dr].s11 + aint[fiu_dr].s13) % MOD;
sum = (sum + aint[fiu_dr].s30 + aint[fiu_dr].s31 + aint[fiu_dr].s33) % MOD;
if (v[st] == 1){
aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
aint[nod].s13 = (aint[nod].s13 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
if (v[mid] == 1){
/// trebuie sa mai scad cv
aint[nod].s10 -= aint[fiu_dr].s30;
if (aint[nod].s10 < 0) aint[nod].s10 += MOD;
aint[nod].s11 -= aint[fiu_dr].s31;
if (aint[nod].s11 < 0) aint[nod].s11 += MOD;
aint[nod].s13 -= aint[fiu_dr].s33;
if (aint[nod].s13 < 0) aint[nod].s13 += MOD;
}
} else {
if (v[st] == 3){
aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
if (v[mid] == 1){
/// trebuie sa mai scad cv
aint[nod].s30 -= aint[fiu_dr].s30;
if (aint[nod].s30 < 0) aint[nod].s30 += MOD;
aint[nod].s31 -= aint[fiu_dr].s31;
if (aint[nod].s31 < 0) aint[nod].s31 += MOD;
aint[nod].s33 -= aint[fiu_dr].s33;
if (aint[nod].s33 < 0) aint[nod].s33 += MOD;
}
} else { /// altceva => 0
aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD;
aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD;
aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD;
if (v[mid] == 1){
/// trebuie sa mai scad cv
aint[nod].s00 -= aint[fiu_dr].s30;
if (aint[nod].s00 < 0) aint[nod].s00 += MOD;
aint[nod].s01 -= aint[fiu_dr].s31;
if (aint[nod].s01 < 0) aint[nod].s01 += MOD;
aint[nod].s03 -= aint[fiu_dr].s33;
if (aint[nod].s03 < 0) aint[nod].s03 += MOD;
}
}
}
}
void build (int nod, int st, int dr){
if (st == dr){
if (v[st] == 0)
return;
if (v[st] == 1){
aint[nod].s00 = 1;
return;
}
if (v[st] == 2){
aint[nod].s00 = 1, aint[nod].s11 = 1;
return;
}
if (v[st] == 3){
aint[nod].s00 = 2, aint[nod].s11 = 1;
return;
}
aint[nod].s11 = aint[nod].s33 = 1;
aint[nod].s00 = v[st] - 2;
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
update_node (nod,st,dr);
}
void update (int nod, int st, int dr, int poz, int val){
if (st == dr){
if (val == 0)
return;
if (val == 1){
aint[nod].s00 = 1;
return;
}
if (val == 2){
aint[nod].s00 = 1, aint[nod].s11 = 1;
return;
}
if (val == 3){
aint[nod].s00 = 2, aint[nod].s11 = 1;
return;
}
aint[nod].s11 = aint[nod].s33 = 1;
aint[nod].s00 = val - 2;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
update_node (nod,st,dr);
}
void query (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y){
/// vreau sa adaug intervalul asta la solutie
long long sol_aux0 = 0, sol_aux1 = 0, sol_aux3 = 0;
/// daca iau toate nr din intervalul asta mai mici, restul le completez cu dp
if (!_first){
_first = 1;
sol0 = (aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD;
sol1 = (aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD;
sol3 = (aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD;
} else {
int nr = y - dr; /// cate am dupa
sol_aux0 = (sol_aux0 + 1LL*sol0*(aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD)%MOD;
sol_aux0 = (sol_aux0 + 1LL*sol3*(aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD)%MOD;
sol_aux0 = (sol_aux0 + 1LL*sol1*(aint[nod].s00 + aint[nod].s10)%MOD)%MOD;
sol_aux1 = (sol_aux1 + 1LL*sol0*(aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD)%MOD;
sol_aux1 = (sol_aux1 + 1LL*sol3*(aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD)%MOD;
sol_aux1 = (sol_aux1 + 1LL*sol1*(aint[nod].s01 + aint[nod].s11)%MOD)%MOD;
sol_aux3 = (sol_aux3 + 1LL*sol0*(aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD)%MOD;
sol_aux3 = (sol_aux3 + 1LL*sol3*(aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD)%MOD;
sol_aux3 = (sol_aux3 + 1LL*sol1*(aint[nod].s03 + aint[nod].s13)%MOD)%MOD;
/// in cazul asta pot sa am orice stare pt ca nu influenteaza cu nmc
int sum = (dp[nr].s00 + dp[nr].s01 + dp[nr].s03)%MOD;
sum = (sum + dp[nr].s10 + dp[nr].s11 + dp[nr].s13)%MOD;
sum = (sum + dp[nr].s30 + dp[nr].s31 + dp[nr].s33)%MOD;
sol_aux0 = (1LL * sol_aux0 * sum) % MOD;
sol_aux3 = (1LL * sol_aux3 * sum) % MOD;
sum = (dp[nr].s00 + dp[nr].s01 + dp[nr].s03)%MOD;
sum = (dp[nr].s10 + dp[nr].s11 + dp[nr].s13)%MOD;
sol_aux1 = (1LL * sol_aux1 * sum) % MOD;
sol0 = sol_aux0;
sol1 = sol_aux1;
sol3 = sol_aux3;
}
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>q;
for (i=1;i<=n;i++){
cin>>ch;
v[i] = ch - '0';
}
/// dp[i].stare - cate nr de i cifre pot forma care au starea stare
dp[1].s11 = dp[1].s33 = 1;
dp[1].s00 = 8;
for (i=2;i<=n;i++){
dp[i].s00 = 8 * (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD;
dp[i].s01 = (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD;
dp[i].s03 = (dp[i-1].s00 + dp[i-1].s03) % MOD;
dp[i].s10 = 8 * (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD;
dp[i].s11 = (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD;
dp[i].s13 = (dp[i-1].s10 + dp[i-1].s13) % MOD;
dp[i].s30 = 8 * (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD;
dp[i].s31 = (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD;
dp[i].s33 = (dp[i-1].s30 + dp[i-1].s33) % MOD;
}
build (1,1,n);
sol0 = sol1 = sol3 = _first = 0;
query(1,1,n,1,n);
cout<<(sol0 + sol1 + sol3 + 1)%MOD<<"\n";
/// aint[nod] - cate nr mai mici sau egale decat intervalul ala pot forma
for (;q--;){
cin>>c>>x>>y;
if (c == 1){ /// query
sol0 = sol1 = sol3 = _first = 0;
query (1,1,n,x,y);
cout<<(sol0 + sol1 + sol3 + 1)%MOD<<"\n";
} else {
v[x] = y;
update (1,1,n,x,y);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
2168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
39 ms |
2168 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
376 KB |
Output is correct |
| 3 |
Correct |
5 ms |
376 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Incorrect |
39 ms |
2168 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
