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>
using namespace std;
#define pb push_back
#define sz size()
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define int long long
typedef pair < int, int > pii;
typedef vector < int > vi;
typedef vector < vi > vvi;
const int N = 100100;
int mod = 1e9 + 7;
int a[N];
int num (int x) {
if (x == 1) {
return 0;
}
if (x == 3) {
return 1;
}
return 2;
}
void add (int &a, int b) {
a += b;
if (a > mod) {
a -= mod;
}
if (a < 0) {
a += mod;
}
}
int mult (int a, int b) {
return (a * b) % mod;
}
struct node {
int dp[3][3][3];
node() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int f = 0; f < 3; f++) {
dp[i][j][f] = 0;
}
}
}
}
};
node t[4 * N];
void _clear(node &a) {
for (int i = 0; i <= 2; i++)
for (int j = 0; j <= 2; j++)
for (int i1 = 0; i1 <= 2; i1++)
a.dp[i][j][i1] = 0;
}
int sum1[3][3], sum2[3][3];
node recalc (node a, node b) {
node c;
for (int f = 0; f <= 2; f++) {
for (int d = 0; d <= 2; d++) {
sum1[d][f] = sum2[d][f] = 0;
for (int j = 0; j <= 2; j++) {
add(sum1[d][f], a.dp[d][j][f]);
add(sum2[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(sum1[d1][f], sum2[d2][s]));
add(c.dp[d1][d2][nf], -mult(a.dp[d1][0][f], b.dp[1][d2][s]));
}
}
}
}
return c;
}
void build (int v, int l, int r) {
if (l == r) {
for (int i = 0; i <= 9; i++) {
int f = (a[l] < i ? 2 : a[l] == i);
add(t[v].dp[num(i)][num(i)][f], 1);
}
return;
}
int mid = (r + l) / 2;
build(2 * v, l, mid);
build(2 * v + 1, mid + 1, r);
t[v] = recalc(t[2 * v], t[2 * v + 1]);
}
void upd (int v, int l, int r, int pos, int val) {
if (l > pos || r < pos) {
return;
}
if (l == r) {
_clear(t[v]);
for (int i = 0; i <= 9; i++) {
int f = (i > a[l] ? 2 : a[l] == i);
add(t[v].dp[num(i)][num(i)][f], 1);
}
return;
}
int mid = (r + l) / 2;
upd (2 * v, l, mid, pos, val);
upd (2 * v + 1, mid + 1, r, pos, val);
t[v] = recalc(t[2 * v], t[2 * v + 1]);
}
node ans;
int used;
void get (int v, int l, int r, int tl, int tr) {
if (l > tr || r < tl) {
return;
}
if (l >= tl && r <= tr) {
if (!used) {
ans = t[v];
}
else {
ans = recalc(ans, t[v]);
}
used = 1;
return;
}
int mid = (l + r) / 2;
get (2 * v, l, mid, tl, tr);
get (2 * v + 1, mid + 1, r, tl, tr);
}
int calc_ans (node a) {
int cur = 0;
for (int f = 0; f < 2; f++) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cur += a.dp[i][j][f];
cur %= mod;
}
}
}
return cur;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
char c;
cin >> c;
a[i] = c - '0';
}
build (1, 1, n);
get(1, 1, n, 1, n);
cout << calc_ans(ans) << "\n";
while (q--) {
int type;
cin >> type;
if (type == 1) {
int l, r;
cin >> l >> r;
used = 0;
_clear(ans);
get(1, 1, n, l, r);
cout << calc_ans(ans) << "\n";
}
else {
int pos, x;
cin >> pos >> x;
a[pos] = x;
upd(1, 1, n, pos, x);
}
}
}
# | 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... |