Overview

Consider each declaration as a constraint “the XOR of the two team numbers is \(c\).”
After each operation, find the number of ways to replace X with 0/1 such that the overall system is consistent.

Analysis

Let \(t_i \in \{0,1\}\) denote the team that person \(i\) belongs to.
A declaration \((u,v,c)\) becomes the following constraint:

\[ t_u \oplus t_v = c \]

• \(c=0\): same team
• \(c=1\): different teams

Therefore, looking only at the determined declarations, this becomes a “XOR constraint consistency check.”
This can be determined using a weighted Union-Find (Parity DSU).

---

On the other hand, trying all possibilities for X declarations results in \(2^x\) cases when there are \(x\) occurrences of X, which is far too many.
Instead, we count using the following property.

For all current declarations, define:

• \(G_{\text{all}}\): the graph with all declarations (including X) as edges
• \(G_{\text{fix}}\): the graph with only declarations whose content is 0 or 1 as edges

Also, define:

\[ \operatorname{rank}(G) = N - \text{number of connected components} \]

First, if there is already a contradiction among the determined declarations, then no valid assignment exists regardless of how X is filled in, so the answer is \(0\).

If there is no contradiction among the determined declarations, the answer is:

\[ 2^{\operatorname{rank}(G_{\text{all}}) - \operatorname{rank}(G_{\text{fix}})} \]

Written in terms of connected components, this is:

\[ 2^{\text{connected components}(G_{\text{fix}}) - \text{connected components}(G_{\text{all}})} \]

---

Let’s understand why this formula holds.

When looking only at the determined declarations, within each connected component, the relative team relationships between people are already fixed.
However, flipping the entire connected component between teams \(0/1\) does not change whether the declarations are satisfied.

The X edges can be thought of as edges connecting these determined components.
Suppose a connected component of \(G_{\text{all}}\) contains \(s\) connected components of \(G_{\text{fix}}\).

For each of these \(s\) components, we can choose whether to flip it or not, which determines the values of X.
However, flipping all of them together does not change the XOR of any edge, so it does not produce a different valid assignment.

Therefore, the degrees of freedom from this connected component is:

\[ 2^{s-1} \]

Multiplying this across all connected components of \(G_{\text{all}}\) gives:

\[ 2^{\text{connected components}(G_{\text{fix}}) - \text{connected components}(G_{\text{all}})} \]

For example, if all 3 edges of a triangle on 3 vertices are X, the valid assignments are only those where the XOR around the cycle is \(0\).
In this case, the rank of \(G_{\text{all}}\) is \(2\) and the rank of \(G_{\text{fix}}\) is \(0\), so the answer is \(2^2=4\) ways.

Algorithm

After each operation, recompute the answer by reviewing all currently existing declarations from scratch.
Since \(N,Q \leq 3000\), recomputing each time is fast enough.

The computation after each operation proceeds as follows:

1. Prepare a regular Union-Find all

   • For all declarations including X, connect endpoints \(u,v\)
   • This gives the number of connected components of \(G_{\text{all}}\)

2. Prepare a Parity DSU fixed

   • Add only declarations whose content is 0 or 1
   • Check whether there is a contradiction in the constraint \(t_u \oplus t_v = c\)
   • If there is a contradiction, the answer is \(0\)

3. If there is no contradiction:

\[ \operatorname{rank}_{\text{all}} = N - \text{number of connected components in all} \]

\[ \operatorname{rank}_{\text{fix}} = N - \text{number of connected components in fixed} \]

Output:

\[ 2^{\operatorname{rank}_{\text{all}} - \operatorname{rank}_{\text{fix}}} \]

For the R k operation, look at the current content of declaration \(k\), add \(1\) to it, and overwrite declaration \(k+1\).

• 0 → 1
• 1 → 0
• X → X

Since declaration contents change over time, manage the current content of each declaration in an array.

Complexity

• Time complexity: \(O(Q(N+Q)\alpha(N))\)
• Space complexity: \(O(N+Q)\)

Here \(\alpha(N)\) is the inverse Ackermann function of Union-Find, which can be treated as practically constant.

Implementation Notes

• Person numbers in the input are 1-indexed, so convert to 0-indexed in the implementation.

• In R k, \(k\) is a 1-indexed declaration number.

  • Declaration \(k\) is edges[k-1]
  • Declaration \(k+1\) is edges[k]

• In Parity DSU, each vertex maintains the “XOR to its parent.”

  • find(x) returns the root and the “XOR from \(x\) to the root.”
  • When adding a constraint within the same connected component, if it doesn’t match the existing XOR, there is a contradiction.

• Multiple edges are not a problem.

  • Multiple declarations between the same two vertices are correctly handled by the Parity DSU as contradiction checks.

    Source Code

#include <bits/stdc++.h>
using namespace std;

static const long long MOD = 998244353;

struct Edge {
    int u, v;
    char c;
};

struct DSU {
    vector<int> p, sz;
    int comps;

    DSU(int n) : p(n), sz(n, 1), comps(n) {
        iota(p.begin(), p.end(), 0);
    }

    int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        comps--;
    }
};

struct ParityDSU {
    vector<int> p, sz, xr;
    int comps;

    ParityDSU(int n) : p(n), sz(n, 1), xr(n, 0), comps(n) {
        iota(p.begin(), p.end(), 0);
    }

    pair<int, int> find(int x) {
        if (p[x] == x) return {x, 0};
        auto [r, v] = find(p[x]);
        xr[x] ^= v;
        p[x] = r;
        return {p[x], xr[x]};
    }

    bool unite(int a, int b, int w) {
        auto [ra, xa] = find(a);
        auto [rb, xb] = find(b);

        if (ra == rb) {
            return ((xa ^ xb) == w);
        }

        if (sz[ra] < sz[rb]) {
            swap(ra, rb);
            swap(xa, xb);
        }

        p[rb] = ra;
        xr[rb] = xa ^ xb ^ w;
        sz[ra] += sz[rb];
        comps--;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<long long> pow2(N + Q + 10, 1);
    for (int i = 1; i < (int)pow2.size(); i++) {
        pow2[i] = pow2[i - 1] * 2 % MOD;
    }

    vector<Edge> edges;

    auto calc = [&]() -> long long {
        DSU all(N);
        ParityDSU fixed(N);
        bool ok = true;

        for (const auto &e : edges) {
            all.unite(e.u, e.v);

            if (e.c != 'X') {
                int w = e.c - '0';
                if (!fixed.unite(e.u, e.v, w)) {
                    ok = false;
                }
            }
        }

        if (!ok) return 0;

        int rank_all = N - all.comps;
        int rank_fixed = N - fixed.comps;
        return pow2[rank_all - rank_fixed];
    };

    for (int qi = 0; qi < Q; qi++) {
        string op;
        cin >> op;

        if (op == "A") {
            int u, v;
            char c;
            cin >> u >> v >> c;
            --u;
            --v;
            edges.push_back({u, v, c});
        } else {
            int k;
            cin >> k;
            char c = edges[k - 1].c;
            if (c == '0') c = '1';
            else if (c == '1') c = '0';
            edges[k].c = c;
        }

        cout << calc() << '\n';
    }

    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.