#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
int n, q;
char s[N];
int dp[N];
struct ura{
int cnt, cnt1, cnt3, cnt31, are1, are3, are31, eok, nr;
///cnt -> cate cu prop aia
} seg[N * 4];
ura join(ura a, ura b)
{
ura rez;
rez.are1 = rez.are31 = rez.are3 = rez.cnt1 = rez.cnt31 = rez.cnt3 = rez.cnt = rez.eok = rez.nr = 0;
if (!(a.are1 && b.are3))
{
if (a.eok && b.eok)
rez.eok = 1;
if (a.are3 && b.are1)
rez.are31 = 1;
if (a.are3 && b.eok)
rez.are3 = 1;
if (b.are1 && a.eok)
rez.are1 = 1;
}
rez.cnt = (a.cnt - a.eok) * dp[b.nr] + a.eok * b.cnt - (a.cnt1 - a.are1) * dp[b.nr - 1] - b.cnt3 * a.are1;
rez.cnt1 = (a.cnt - a.eok) * dp[b.nr - 1] + b.cnt1 * a.eok - (a.cnt1 - a.are1) * dp[b.nr - 2] - b.cnt31 * a.are1;
rez.cnt3 = (a.cnt3 - a.are3) * dp[b.nr] + b.cnt * a.are3 - (a.cnt31 - a.are31) * dp[b.nr - 1] - b.cnt3 * a.are31;
rez.cnt31 = (a.cnt3 - a.are3) * dp[b.nr - 1] + b.cnt1 * a.are3 - (a.cnt31 - a.are31) * dp[b.nr - 2] - b.cnt31 * a.are31;
rez.nr = a.nr + b.nr;
return rez;
}
int adun(int a, int b)
{
int c = a + b;
if (c >= mod)
c -= mod;
return c;
}
int inm(int a, int b)
{
ll aa = a;
ll bb = b;
ll c = aa * bb;
c = c % mod;
return c;
}
int scad(int a, int b)
{
int c = a - b;
if (c < 0)
c += mod;
return c;
}
void leaf(int nod, int val)
{
seg[nod].are1 = seg[nod].are31 = seg[nod].are3 = seg[nod].cnt1 = seg[nod].cnt3 = seg[nod].cnt31 = 0;
seg[nod].nr = 1;
seg[nod].eok = 1;
if (val == 1)
seg[nod].are1 = 1;
if (val == 3)
seg[nod].are3 = 1;
if (1 <= val)
seg[nod].cnt1 = 1;
if (3 <= val)
seg[nod].cnt3 = 1;
seg[nod].cnt = val + 1;
return;
}
void upd(int nod, int l, int r, int poz, int val)
{
if (l == r)
{
leaf(nod, val);
return;
}
int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
if (poz <= mid)
upd(ls, l, mid, poz, val);
else
upd(rs, 1 + mid, r, poz, val);
seg[nod] = join(seg[ls], seg[rs]);
}
ura qry(int nod, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
return seg[nod];
int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
if (mid < ql)
return qry(rs, mid + 1, r, ql, qr);
else
if (qr <= mid)
return qry(ls, l, mid, ql, qr);
else
return join(qry(ls, l, mid, ql, qr), qry(rs, mid + 1, r, ql, qr));
}
void build(int nod, int l, int r)
{
if (l == r)
{
leaf(nod, s[l] - '0');
return;
}
int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1;
build(ls, l, mid);
build(rs, mid + 1, r);
seg[nod] = join(seg[ls], seg[rs]);
}
int main()
{
cin >> n >> q;
cin >> s + 1;
dp[0] = 1;
dp[1] = 10;
for (int i = 2; i <= n; i++)
dp[i] = scad(inm(dp[i - 1], 10) , dp[i - 2]);
build(1, 1, n);
cout << qry(1, 1, n, 1, n).cnt << '\n';
while (q--)
{
int t, a, b;
cin >> t >> a >> b;
if (t == 1)
{
cout << qry(1, 1, n, a, b).cnt << '\n';
continue;
}
upd(1, 1, n, a, b);
}
return 0;
}
Compilation message
lucky.cpp: In function 'int main()':
lucky.cpp:119:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
119 | cin >> s + 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
