fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. static const ll NEG = -(1LL << 60);
  7. static const int MOD = 998244353;
  8. static const int s = 6; // 3 regex states * 2 bits prev-selected
  9.  
  10. struct cell {
  11.     ll val;
  12.     int cnt;
  13. };
  14.  
  15. struct mat {
  16.     cell a[s][s];
  17. };
  18.  
  19. int n, q;
  20. vector<ll> a;
  21. vector<int> col;
  22.  
  23. int id(int r, int p) {
  24.     return r * 2 + p;
  25. }
  26.  
  27. int go[3][3];
  28.  
  29. cell make_cell(ll v = NEG, int c = 0) {
  30.     return {v, c};
  31. }
  32.  
  33. void relax(cell &x, ll v, int c) {
  34.     if (c == 0) return;
  35.     if (v > x.val) {
  36.         x.val = v;
  37.         x.cnt = c;
  38.     } else if (v == x.val) {
  39.         x.cnt += c;
  40.         if (x.cnt >= MOD) x.cnt -= MOD;
  41.     }
  42. }
  43.  
  44. mat identity_mat() {
  45.     mat m;
  46.     for (int i = 0; i < s; ++i) {
  47.         for (int j = 0; j < s; ++j) m.a[i][j] = make_cell();
  48.         m.a[i][i] = {0, 1};
  49.     }
  50.     return m;
  51. }
  52.  
  53. mat leaf_mat(ll val, int c) {
  54.     mat m;
  55.     for (int i = 0; i < s; ++i) {
  56.         for (int j = 0; j < s; ++j) m.a[i][j] = make_cell();
  57.     }
  58.  
  59.     for (int r = 0; r < 3; ++r) {
  60.         for (int p = 0; p < 2; ++p) {
  61.             int from = id(r, p);
  62.  
  63.             // skip current position
  64.             int to_skip = id(r, 0);
  65.             relax(m.a[from][to_skip], 0, 1);
  66.  
  67.             // take current position
  68.             if (p == 0) {
  69.                 int nr = go[r][c];
  70.                 if (nr != -1) {
  71.                     int to_take = id(nr, 1);
  72.                     relax(m.a[from][to_take], val, 1);
  73.                 }
  74.             }
  75.         }
  76.     }
  77.     return m;
  78. }
  79.  
  80. mat merge_mat(const mat &l, const mat &r) {
  81.     mat res;
  82.     for (int i = 0; i < s; ++i) {
  83.         for (int j = 0; j < s; ++j) res.a[i][j] = make_cell();
  84.     }
  85.  
  86.     for (int i = 0; i < s; ++i) {
  87.         for (int k = 0; k < s; ++k) {
  88.             if (l.a[i][k].cnt == 0) continue;
  89.             for (int j = 0; j < s; ++j) {
  90.                 if (r.a[k][j].cnt == 0) continue;
  91.                 ll nv = l.a[i][k].val + r.a[k][j].val;
  92.                 int nc = int((1LL * l.a[i][k].cnt * r.a[k][j].cnt) % MOD);
  93.                 relax(res.a[i][j], nv, nc);
  94.             }
  95.         }
  96.     }
  97.  
  98.     return res;
  99. }
  100.  
  101. struct segtree {
  102.     int sz;
  103.     vector<mat> st;
  104.  
  105.     segtree() {}
  106.     segtree(int n) { init(n); }
  107.  
  108.     void init(int n) {
  109.         sz = 1;
  110.         while (sz < n) sz <<= 1;
  111.         st.assign(sz << 1, identity_mat());
  112.     }
  113.  
  114.     void build(const vector<ll> &arr, const vector<int> &c) {
  115.         int n = (int)arr.size() - 1;
  116.         for (int i = 0; i < n; ++i) st[sz + i] = leaf_mat(arr[i + 1], c[i + 1]);
  117.         for (int i = sz - 1; i >= 1; --i) st[i] = merge_mat(st[i << 1], st[i << 1 | 1]);
  118.     }
  119.  
  120.     void update_val(int pos, ll val, int c) {
  121.         int p = sz + pos - 1;
  122.         st[p] = leaf_mat(val, c);
  123.         for (p >>= 1; p; p >>= 1) st[p] = merge_mat(st[p << 1], st[p << 1 | 1]);
  124.     }
  125.  
  126.     void update_col(int pos, ll val, int c) {
  127.         update_val(pos, val, c);
  128.     }
  129.  
  130.     pair<ll, int> answer() const {
  131.         int start = id(0, 0);
  132.         ll best = NEG;
  133.         int ways = 0;
  134.         for (int t = 0; t < s; ++t) {
  135.             const cell &x = st[1].a[start][t];
  136.             if (x.cnt == 0) continue;
  137.             if (x.val > best) {
  138.                 best = x.val;
  139.                 ways = x.cnt;
  140.             } else if (x.val == best) {
  141.                 ways += x.cnt;
  142.                 if (ways >= MOD) ways -= MOD;
  143.             }
  144.         }
  145.         return {best, ways};
  146.     }
  147. };
  148.  
  149. int main() {
  150.     ios::sync_with_stdio(false);
  151.     cin.tie(nullptr);
  152.  
  153.     go[0][0] = 0;
  154.     go[0][1] = 1;
  155.     go[0][2] = -1;
  156.     go[1][0] = 2;
  157.     go[1][1] = 1;
  158.     go[1][2] = -1;
  159.     go[2][0] = 2;
  160.     go[2][1] = -1;
  161.     go[2][2] = -1;
  162.  
  163.     cin >> n >> q;
  164.     a.assign(n + 1, 0);
  165.     col.assign(n + 1, 0);
  166.  
  167.     for (int i = 1; i <= n; ++i) cin >> a[i];
  168.     for (int i = 1; i <= n; ++i) cin >> col[i];
  169.  
  170.     segtree st(n);
  171.     st.build(a, col);
  172.  
  173.     while (q--) {
  174.         int tp;
  175.         cin >> tp;
  176.         if (tp == 1) {
  177.             int x;
  178.             ll y;
  179.             cin >> x >> y;
  180.             a[x] = y;
  181.             st.update_val(x, a[x], col[x]);
  182.         } else if (tp == 2) {
  183.             int x, y;
  184.             cin >> x >> y;
  185.             col[x] = y;
  186.             st.update_col(x, a[x], col[x]);
  187.         } else {
  188.             auto [mx, ways] = st.answer();
  189.             cout << mx << ' ' << ways << '\n';
  190.         }
  191.     }
  192.  
  193.     return 0;
  194. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QYzbGY
language:
C++14 (gcc 8.3)
created:
1 day 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!