Overview

Each declaration is treated as a constraint “the XOR of the two team numbers is \(c\).”
We use Union-Find to check whether the fixed declarations alone are consistent, and determine the number of valid assignments for undetermined X declarations from the number of connected components.

Analysis

We represent each person’s team membership as either \(0\) or \(1\).
Then, a declaration \((u, v, c)\) becomes the following constraint:

\[ team_u \oplus team_v = c \]

where \(\oplus\) denotes XOR.

Considering only fixed declarations

First, looking only at declarations with content 0 or 1, this forms a set of XOR constraints.

For example:

• \(u\) and \(v\) are on the same team: \(team_u \oplus team_v = 0\)
• \(u\) and \(v\) are on different teams: \(team_u \oplus team_v = 1\)

Such constraints can be checked for contradictions using a Weighted Union-Find (Parity Union-Find).

If the relative relationship between \(u\) and \(v\) is already determined, a contradiction occurs if the new constraint disagrees.
If the fixed declarations alone are contradictory, then no matter how we fill in the Xs, the overall constraints cannot be satisfied, so the answer is \(0\).

We cannot simply count the number of Xs

Just because there are \(x\) declarations with content X does not mean the answer is simply \(2^x\).

For example, if all 3 edges of a triangle are X, the XOR of the 3 edge values must be \(0\).
Therefore, not all \(2^3 = 8\) possibilities are valid — there are only \(4\) valid assignments.

In other words, constraints also arise among X declarations through cycles.

Number of valid assignments

Consider the graph formed by only the fixed declarations, and let its number of connected components be \(C\).
Also, let the number of connected components in the graph formed by all declarations (including X) be \(D\).

Assume the fixed declarations have no contradictions.

Within each connected component of fixed declarations, the relative team relationships are determined.
However, flipping the entire connected component (inverting all assignments) still satisfies all fixed declarations.

That is, for each connected component of fixed declarations, there is a degree of freedom of “flip or not flip.”

On the other hand, X declarations connect these connected components together.
Within a single connected component that includes all declarations, flipping the entire component does not change the values that go into the X positions.

Therefore, if a single connected component in the graph of all declarations contains \(t\) connected components from the fixed declarations, the number of valid assignments is

\[ 2^{t-1} \]

Multiplying this across all connected components gives:

\[ 2^{C-D} \]

Therefore:

• If the fixed declarations alone have a contradiction, the answer is \(0\)
• If there is no contradiction, the answer is \(2^{C-D}\)

Algorithm

After each operation, we compute the answer for the current state.

Since the constraints are \(N, Q \leq 3000\), rebuilding the Union-Find each time is fast enough.

Information to maintain

For each declaration, we maintain the following in arrays:

• us[i]: one person in declaration \(i\)
• vs[i]: the other person in declaration \(i\)
• cont[i]: current content
  • 0
  • 1
  • 2: X

Additionally, the number of connected components \(D\) in the graph that considers all declarations (without ignoring any) is managed with a regular Union-Find.

Since R operations do not change edge endpoints, the number of connected components \(D\) in the full declaration graph does not change.
We only union the two vertices when a declaration is added via an A operation.

Processing each operation

A u v c

1. Add the declaration to the arrays
2. Union \(u, v\) in the Union-Find that includes all declarations

R k

Look at the current content of declaration \(k\), and overwrite declaration \(k+1\):

• 0 becomes 1
• 1 becomes 0
• X remains X

Computing the answer

After each operation, do the following:

1. Initialize the Parity Union-Find
2. Iterate through all current declarations
3. Skip declarations with content X
4. Add declarations with content 0 or 1 as XOR constraints
5. If there is a contradiction, the answer is \(0\)
6. If there is no contradiction, let \(C\) be the number of connected components in the fixed declaration graph, and the answer is

\[ 2^{C-D} \]

Complexity

If the current number of declarations is \(M\), the recomputation after each operation takes

\[ O(N + M \alpha(N)) \]

Since \(M \leq Q\), the overall complexity is

\[ O(Q(N + Q)\alpha(N)) \]

This is sufficiently fast for the constraints \(N, Q \leq 3000\).

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

Implementation notes

In the Parity Union-Find, each vertex stores the “XOR with its parent.”

find(x) returns:

• The root
• The XOR from \(x\) to the root

When adding the constraint

\[ team_u \oplus team_v = c \]

if they are already in the same connected component, we check whether the currently known XOR matches \(c\).

If they differ, there is a contradiction.

If they are in different connected components, we merge one into the other and set the XOR relationship between the roots accordingly.

Also, note that the R operation references “the current content of declaration \(k\).”
It uses the value after all previous R operations have been applied, not the original content.

Source Code

import sys

MOD = 998244353

def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())

    pow2 = [1] * (N + Q + 5)
    for i in range(1, len(pow2)):
        pow2[i] = (pow2[i - 1] * 2) % MOD

    us = []
    vs = []
    cont = []  # 0, 1, 2(X)

    parent_all = list(range(N))
    size_all = [1] * N
    comp_all = N

    def find_all(x):
        while parent_all[x] != x:
            parent_all[x] = parent_all[parent_all[x]]
            x = parent_all[x]
        return x

    def union_all(a, b):
        nonlocal comp_all
        ra = find_all(a)
        rb = find_all(b)
        if ra == rb:
            return
        if size_all[ra] < size_all[rb]:
            ra, rb = rb, ra
        parent_all[rb] = ra
        size_all[ra] += size_all[rb]
        comp_all -= 1

    def solve_current():
        parent = list(range(N))
        size = [1] * N
        parity = [0] * N
        comp = N
        ok = True

        def find(x):
            r = x
            acc = 0
            while parent[r] != r:
                acc ^= parity[r]
                r = parent[r]

            root = r
            cur = x
            val = acc
            while parent[cur] != cur:
                p = parent[cur]
                d = parity[cur]
                parent[cur] = root
                parity[cur] = val
                val ^= d
                cur = p

            return root, acc

        nonlocal_us = us
        nonlocal_vs = vs
        nonlocal_cont = cont

        for i, c in enumerate(nonlocal_cont):
            if c == 2:
                continue

            a = nonlocal_us[i]
            b = nonlocal_vs[i]
            ra, xa = find(a)
            rb, xb = find(b)

            if ra == rb:
                if (xa ^ xb) != c:
                    ok = False
            else:
                if size[ra] < size[rb]:
                    ra, rb = rb, ra
                    xa, xb = xb, xa
                parent[rb] = ra
                parity[rb] = xa ^ xb ^ c
                size[ra] += size[rb]
                comp -= 1

        if not ok:
            return 0
        return pow2[comp - comp_all]

    out = []

    for _ in range(Q):
        parts = input().split()
        if parts[0] == b'A':
            u = int(parts[1]) - 1
            v = int(parts[2]) - 1
            ch = parts[3]
            if ch == b'X':
                c = 2
            else:
                c = ch[0] - 48

            us.append(u)
            vs.append(v)
            cont.append(c)
            union_all(u, v)
        else:
            k = int(parts[1]) - 1
            c = cont[k]
            if c == 2:
                cont[k + 1] = 2
            else:
                cont[k + 1] = c ^ 1

        out.append(str(solve_current()))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.