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 ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
const ll INF = 1e9;
int n;
struct node {
bool has13;
int st, dr;
int cnt[4][4];
} aint[400002];
int v[100002];
int smaller[100002][4][4], q;
node merge (node fiu1, node fiu2) {
node p;
p.has13 = fiu1.has13 | fiu2.has13 | (v[fiu1.dr] == 1 && v[fiu2.st] == 3);
/// caz1 prima bucata e mai mica
memset(p.cnt, 0, sizeof(p.cnt));
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
for (int k = 1; k <= 3; k++)
for (int t = 1; t <= 3; t++) {
if (j == 1 && k == 3)
continue;
p.cnt[i][t] += 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] % mod;
// if (fiu1.dr == 2) {
// cout << i << " " << t << "\n";
// cout << i << " " << j << " " << fiu1.cnt[i][j] << "\n";
// cout << k << " " << t << " " << smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n";
// cout << 1ll * fiu1.cnt[i][j] * smaller[fiu2.dr - fiu2.st + 1][k][t] << "\n\n";
// }
// assert(p.cnt[i][j] >= 0);
if (p.cnt[i][t] >= mod)
p.cnt[i][t] -= mod;
}
int c1 = v[fiu1.st];
if (c1 != 1 && c1 != 3) c1 = 2;
int c2 = v[fiu1.dr];
if (c2 != 1 && c2 != 3) c2 = 2;
if (fiu1.has13 == 0)
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++) {
if (c2 == 1 && i == 3)
continue;
p.cnt[c1][j] += fiu2.cnt[i][j];
if (p.cnt[c1][j] >= mod)
p.cnt[c1][j] -= mod;
}
// int c3 = v[fiu2.dr];
//if (c3 != 1 && c3 != 3) c3 = 2;
//if (!p.has13) {
//p.cnt[c1][c3]++;
//if (p.cnt[c1][c3] >= mod) p.cnt[c1][c3] -= mod;
//}
p.st = fiu1.st;
p.dr = fiu2.dr;
return p;
}
void update (int nod, int st, int dr, int poz, int a) {
if (st == dr) {
memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
aint[nod].has13 = 0;
for (int i = 0; i < a; i++)
if (i == 1 || i == 3)
aint[nod].cnt[i][i] = 1;
else
aint[nod].cnt[2][2]++;
return;
}
int mid = (st + dr) / 2;
if (poz <= mid)
update(2 * nod, st, mid, poz, a);
else
update(2 * nod + 1, mid + 1, dr, poz, a);
aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
void build (int nod, int st, int dr) {
aint[nod].st = st;
aint[nod].dr = dr;
if (st == dr) {
memset(aint[nod].cnt, 0, sizeof(aint[nod].cnt));
aint[nod].has13 = 0;
for (int i = 0; i < v[st]; i++)
if (i == 1 || i == 3)
aint[nod].cnt[i][i] = 1;
else
aint[nod].cnt[2][2]++;
return;
}
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}
node ans;
void query (int nod, int st, int dr, int a, int b) {
if (a <= st && dr <= b) {
if (ans.st == 0)
ans = aint[nod];
else
ans = merge(ans, aint[nod]);
return;
}
int mid = (st + dr) / 2;
if (a <= mid)
query(2 * nod, st, mid, a, b);
if (mid < b)
query(2 * nod + 1, mid + 1, dr, a, b);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> q;
smaller[1][1][1] = 1;
smaller[1][3][3] = 1;
smaller[1][2][2] = 8;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= 3; j++)
for (int k = 1; k <= 3; k++)
for (int t = 1; t <= 3; t++) {
if (k == 1 && t == 3)
continue;
smaller[i][j][t] += 1ll * smaller[i - 1][j][k] * ((t == 1 || t == 3) ? 1 : 8) % mod;
if (smaller[i][j][t] >= mod)
smaller[i][j][t] -= mod;
//assert(smaller[i][j][t] >= 0);
}
}
string s;
cin >> s;
for (int i = 0; i < n; i++)
v[i + 1] = s[i] - '0';
build(1, 1, n);
int sol = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++) {
// assert(aint[1].cnt[i][j] >= 0);
sol = (sol + aint[1].cnt[i][j]);
if (sol >= mod) sol -= mod;
}
cout << (sol + !aint[1].has13) % mod << "\n";
while (q--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) {
ans.st = 0;
query(1, 1, n, x, y);
int sol = 0;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++) {
sol = (sol + ans.cnt[i][j]);
if (sol >= mod) sol -= mod;
}
cout << (sol + !ans.has13) % mod << "\n";
}
else {
update(1, 1, n, x, y);
v[x] = y;
}
}
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... |