fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define endl     '\n'
  5. #define int      long long
  6.  
  7. const int N = 2e5, oo = 2e18, MOD = 1e9+7;
  8.  
  9. typedef array<int, 4> mat;
  10.  
  11. mat mul(const mat& a, const mat& b) {
  12.     mat ret;
  13.     ret[0] = (a[0] * b[0] % MOD + a[1] * b[2] % MOD) % MOD;
  14.     ret[1] = (a[0] * b[1] % MOD + a[1] * b[3] % MOD) % MOD;
  15.     ret[2] = (a[2] * b[0] % MOD + a[3] * b[2] % MOD) % MOD;
  16.     ret[3] = (a[2] * b[1] % MOD + a[3] * b[3] % MOD) % MOD;
  17.     return ret;
  18. }
  19.  
  20. class segtree { 
  21. public:
  22.     struct Node {
  23.         mat data;
  24.         Node() {
  25.             data[0] = data[3] = 1;
  26.         }
  27.         void update(char c) {
  28.             switch (c)
  29.             {
  30.             case 'H':
  31.                 data = {1, 0, 1, 0};
  32.                 break;
  33.             case 'S':
  34.             case 'D':
  35.                 data = {0, 1, 0, 1};
  36.                 break;
  37.             case '?':
  38.                 data = {19, 7, 6, 20};
  39.                 break;
  40.             case 'A':
  41.             case 'E':
  42.             case 'O':
  43.             case 'U':
  44.             case 'I':
  45.                 data = {0, 1, 1, 0};
  46.                 break;
  47.  
  48.             default:
  49.                 data = {1, 0, 0, 1};
  50.                 break;
  51.             }
  52.         }
  53.         Node(char c) {
  54.             update(c);
  55.         }
  56.     };
  57.     Node merge(const Node& a, const Node& b) {
  58.         Node ret;
  59.         ret.data = mul(a.data, b.data);
  60.         return ret;
  61.     }
  62.     int tree_size;
  63.     vector<Node> tree;
  64.     segtree(int n)  {
  65.         tree_size = 1;
  66.         while (tree_size < n) tree_size *= 2;
  67.         tree = vector<Node>(tree_size * 2);
  68.     }
  69.     void update(int idx, char c, int nx = 0, int lx = 0, int rx = -1){
  70.         if (rx == -1)
  71.             rx = tree_size;
  72.         if (rx - lx == 1) {
  73.             tree[nx].update(c);
  74.             return;
  75.         }
  76.         int mid = (lx + rx) / 2;
  77.         if (idx < mid) {
  78.             update(idx, c, 2 * nx + 1, lx, mid);
  79.         } else {
  80.             update(idx, c, 2 * nx + 2, mid, rx);
  81.         }
  82.         tree[nx] = merge(tree[2 * nx + 1], tree[2 * nx + 2]);
  83.     }
  84. };
  85.  
  86.  
  87. void solve() {
  88.     int n, q; cin >> n >> q;
  89.     string s; cin >> s;
  90.     segtree st(n);
  91.     for (int i = 0; i < n; i++) {
  92.         st.update(i, s[i]);
  93.     }
  94.  
  95.     cout << st.tree[0].data[0] << endl;
  96.     while (q--) {
  97.         int x; cin >> x;
  98.         char c; cin >> c;
  99.         st.update(x -1, c);
  100.         cout << st.tree[0].data[0] << endl;
  101.  
  102.     }
  103. }
  104.  
  105.  
  106. signed main() {
  107.     ios_base::sync_with_stdio(false); 
  108.     cin.tie(NULL); cout.tie(NULL);
  109.     // #ifndef ONLINE_JUDGE 
  110.     //    freopen("input.txt", "r", stdin); 
  111.     //    freopen("output.txt", "w", stdout); 
  112.     // #endif 
  113.     int t; t = 1;
  114.     // cin >> t;
  115.     while (t--) solve();
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/n9dDS2
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!