位运算：进阶版翻转硬币问题技术咨询

Great question! Let's break down how to tackle this, building on the segment tree with lazy propagation you already know for the original Flipping Coins problem. We have two solid approaches depending on your needs:

Option 1: Adapt Your Existing Segment Tree #

If you already have a segment tree set up for range flips and head count queries, modifying it to output each coin's final state is straightforward:

• Resolve All Lazy Tags First: Before extracting leaf values, you need to fully propagate all pending flip operations down to every leaf node. This means traversing the tree from root to each leaf, applying any pending flips (toggling the state and updating child counts) and clearing the lazy flags as you go.
• Traverse to Collect Leaf States: Once all lazy updates are applied, perform an in-order traversal of the segment tree. Each leaf node directly represents the final state of a single coin (e.g., 1 for heads, 0 for tails, based on your initial setup).

For the propagation step, remember:

• When a node has a pending flip, flip the head count of its children (using child_range_length - current_head_count), toggle their lazy flags, then clear the parent's lazy flag.

Option 2: Difference Array (Simpler for Final State Only) #

If you don't need to handle intermediate queries (like checking head counts mid-operation) and only care about the final state, a difference array is way more efficient (O(M + N) time vs. O(M log N + N log N) for the segment tree):

Here's the step-by-step:

• Initialize a difference array diff of size N+2 (to avoid boundary issues) with all zeros.
• For each flip operation [A, B]:
  • Increment diff[A] by 1 (marks the start of a flip range)
  • Decrement diff[B+1] by 1 (marks the end of the flip range)
• Compute the prefix sum of diff to get the number of times each coin was flipped.
• For each coin:
  • If flip count is odd: its state is flipped from the initial state
  • If even: it stays as the initial state

Example Python Code #

n = int(input())
m = int(input())
diff = [0] * (n + 2)

for _ in range(m):
    a, b = map(int, input().split())
    diff[a] += 1
    diff[b + 1] -= 1

# Calculate flip counts for each coin
current_flips = 0
final_state = []
for i in range(1, n + 1):
    current_flips += diff[i]
    # Assume initial state is all tails (0), heads = 1
    final_state.append(1 if current_flips % 2 == 1 else 0)

print(' '.join(map(str, final_state)))

Which Approach to Pick? #

• Go with the difference array if you only need the final state—its faster, uses less memory, and is easier to code.
• Stick with the segment tree if you need to handle both intermediate head count queries AND extract the final state later. The adaptation is trivial once you have the basic lazy propagation logic in place.

内容的提问来源于stack exchange，提问作者Benn Tan