My Solution
\n/**\n * Time Complexity: O((n + n_queries) * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `colors`\n *       `n_queries` is th
```\n/**\n * Time Complexity: O((n + n_queries) * log(n))\n * Space Complexity: O(n)\n * where `n` is the length of the vector `colors`\n *       `n_queries` is the length of the vector `queries`\n */\nclass Solution {\n private:\n  class FenwickTree {\n   public:\n    FenwickTree(const int n) : tree_(n) {\n    }\n    \n    int read(const int i) const {\n      int ret = 0;\n      for (int index = i; index > 0; index -= index & -index) {\n        ret += tree_[index - 1];\n      }\n      return ret;\n    }\n    \n    void update(const int i, const int delta) {\n      const int n = static_cast<int>(tree_.size());\n      for (int index = i; index <= n; index += index & -index) {\n        tree_[index - 1] += delta;\n      }\n    }\n    \n   private:\n    vector<int> tree_;\n  };\n  \n public:\n  vector<int> numberOfAlternatingGroups(vector<int> &colors, const vector<vector<int>> &queries) {\n    constexpr int type_i = 0;\n    constexpr int type_query = 1;\n    constexpr int size_i = 1;\n    constexpr int index_i = 1;\n    constexpr int color_i = 2;\n    const int n = static_cast<int>(colors.size());\n    FenwickTree group_counts(n);\n    FenwickTree group_sizes(n);\n    set<int> group_ends;\n    for (int previous = -1, i = 0; i < n; ++i) {\n      const int next_i = i == n - 1 ? 0 : i + 1;\n      if (colors[i] == colors[next_i]) {\n        // colors[i] is an ending point of an alternating group\n        group_ends.emplace(i);\n        if (previous != -1) {\n          const int group_size = i - previous;\n          update_group_size(group_counts, group_sizes, group_size, true);\n        }\n        previous = i;\n      }\n    }\n    if (!group_ends.empty()) {\n      const int group_size = n + *group_ends.begin() - *group_ends.rbegin();\n      update_group_size(group_counts, group_sizes, group_size, true);\n    }\n    \n    vector<int> ret;\n    for (const vector<int> &query : queries) {\n      const int type = query[type_i];\n      if (type == type_query) {\n        const int size = query[size_i];\n        ret.emplace_back(do_query(n, group_counts, group_sizes, group_ends, size));\n      } else {\n        const int index = query[index_i];\n        const int color = query[color_i];\n        do_change(colors, group_counts, group_sizes, group_ends, index, color);\n      }\n    }\n    return ret;\n  }\n  \n private:\n  int do_query(const int n,\n               const FenwickTree &group_counts,\n               const FenwickTree &group_sizes,\n               const set<int> &group_ends,\n               const int size) {\n    if (group_ends.empty()) {\n      return n;\n    }\n    \n    const int total_count = group_counts.read(n) - group_counts.read(size - 1);\n    const int total_size = group_sizes.read(n) - group_sizes.read(size - 1);\n    return total_size - (size - 1) * total_count;\n  }\n  \n  void do_change(vector<int> &colors,\n                 FenwickTree &group_counts,\n                 FenwickTree &group_sizes,\n                 set<int> &group_ends,\n                 const int index,\n                 const int color) {\n    if (colors[index] == color) {\n      // no changes\n      return;\n    }\n\n    colors[index] = color;\n    const int n = static_cast<int>(colors.size());\n    const int previous_index = index == 0 ? n - 1 : index - 1;\n    const int next_index = index == n - 1 ? 0 : index + 1;\n    \n    if (colors[previous_index] == colors[index]) {\n      // `previous_index` becomes a new ending point\n      add_end(n, group_counts, group_sizes, group_ends, previous_index);\n    } else {\n      // `previous_index` is no longer an ending point\n      remove_end(n, group_counts, group_sizes, group_ends, previous_index);\n    }\n    \n    if (colors[index] == colors[next_index]) {\n      // `index` becomes a new ending point\n      add_end(n, group_counts, group_sizes, group_ends, index);\n    } else {\n      // `index` is no longer an ending point\n      remove_end(n, group_counts, group_sizes, group_ends, index);\n    }\n  }\n  \n  void add_end(const int n,\n               FenwickTree &group_counts,\n               FenwickTree &group_sizes,\n               set<int> &group_ends,\n               const int index) {\n    if (group_ends.empty()) {\n      update_group_size(group_counts, group_sizes, n, true);\n      group_ends.emplace(index);\n      return;\n    }\n\n    auto itr = group_ends.emplace(index).first;\n    update_end(n, group_counts, group_sizes, group_ends, itr, true);\n  }\n  \n  void remove_end(const int n,\n                  FenwickTree &group_counts,\n                  FenwickTree &group_sizes,\n                  set<int> &group_ends,\n                  const int index) {\n    if (group_ends.size() == 1) {\n      update_group_size(group_counts, group_sizes, n, false);\n      group_ends.clear();\n      return;\n    }\n    \n    auto itr = group_ends.find(index);\n    update_end(n, group_counts, group_sizes, group_ends, itr, false);\n    group_ends.erase(itr);\n  }\n  \n  void update_end(const int n,\n                  FenwickTree &group_counts,\n                  FenwickTree &group_sizes,\n                  set<int> &group_ends,\n                  const set<int>::iterator &itr,\n                  const bool is_adding) {\n    auto previous_itr = itr == group_ends.begin() ? prev(group_ends.end()) : prev(itr);\n    auto next_itr = next(itr) == group_ends.end() ? group_ends.begin() : next(itr);\n    const auto group_size_left = (n + *itr - *previous_itr) % n;\n    const auto group_size_right = (n + *next_itr - *itr) % n;\n    update_group_size(group_counts, group_sizes, group_size_left, is_adding);\n    update_group_size(group_counts, group_sizes, group_size_right, is_adding);\n    update_group_size(group_counts, group_sizes, group_size_left + group_size_right, !is_adding);   \n  }\n  \n  void update_group_size(FenwickTree &group_counts,\n                         FenwickTree &group_sizes,\n                         const int group_size,\n                         const bool is_adding) {\n    const int coefficient = is_adding ? 1 : -1;\n    group_counts.update(group_size, coefficient * 1);\n    group_sizes.update(group_size, coefficient * group_size);\n  }\n};\n```
[]