Untitled
user_9000366
plain_text
2 months ago
3.5 kB
5
Indexable
#include <bits/stdc++.h> using namespace std; #define ll long long void Init() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); #ifdef CLION freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr); #else // freopen("input.txt", "r", stdin); #endif } constexpr int MOD = 1e9 + 7, N = 2; int mul(const ll &a, const ll &b) { return (a % MOD + MOD) * (b % MOD + MOD) % MOD; } int add(const ll &a, const ll &b) { return (a + b + 2 * MOD) % MOD; } typedef vector<vector<int> > matrix; matrix operator*(const matrix &lhs, const matrix &rhs) { int n = lhs.size(); int m = rhs[0].size(); int s1 = lhs[0].size(), s2 = rhs.size(); assert(s1 == s2); matrix ret(n, vector<int>(m)); for (int i = 0; i < n; ++i) for (int j = 0; j < s1; ++j) for (int k = 0; k < m; ++k) ret[i][k] = add(ret[i][k], mul(lhs[i][j], rhs[j][k])); return ret; } matrix Identity(int n) { matrix ret(n, vector<int>(n)); for (int i = 0; i < n; ++i) { ret[i][i] = 1; } return ret; } matrix mat_power(matrix x, ll p) { matrix res = Identity(x.size()); while (p) { if (p & 1) res = (res * x); x = (x * x); p >>= 1; } return res; } matrix calc(char c) { matrix mat(2, vector<int>(2)); for (char i = 'A'; i <= 'Z'; ++i) { if (c == i || c == '?') { if (i == 'H') { mat[0][1] += 1; mat[1][1] += 1; } else if (i == 'S' || i == 'D') { mat[1][0] += 1; mat[0][0] += 1; } else if (i == 'A' || i == 'E' || i == 'I' || i == 'O' || i == 'U') { mat[0][1] += 1; mat[1][0] += 1; } else { mat[0][0] += 1; mat[1][1] += 1; } } } return mat; } struct Tree { struct Node { matrix mat; Node() { mat = Identity(2); } Node(char c) { mat = calc(c); } }; typedef Node T; T f(T a, T b) { Node ret; ret.mat = a.mat * b.mat; return ret; } vector<T> s; int n; Tree(int n = 0) : s(2 * n, Node()), n(n) {} void update(int pos, T val) { for (s[pos += n] = val; pos /= 2;) s[pos] = f(s[pos * 2], s[pos * 2 + 1]); } T query(int b, int e) { e++; T ra = Node(), rb = Node(); for (b += n, e += n; b < e; b /= 2, e /= 2) { if (b % 2) ra = f(ra, s[b++]); if (e % 2) rb = f(s[--e], rb); } return f(ra, rb); } }; void Mesh_JOO() { // n & q <= 2e5 int n, q; cin >> n >> q; string s; cin >> s; Tree st(n); for (int i = 0; i < n; ++i) { st.update(i, Tree::Node(s[i])); } cout << st.query(0, n - 1).mat[1][1] << '\n'; while (q--) { int idx; char c; cin >> idx >> c; idx--; st.update(idx, Tree::Node(c)); cout << st.query(0, n - 1).mat[1][1] << '\n'; } } int main() { Init(); int t{1}; // cin >> t; while (t--) { Mesh_JOO(); } return 0; }
Editor is loading...
Leave a Comment