2178G: deCH OR Dations

We only care about parity. That is the first big simplification: all counts live in $\mathbb F_2$ , so even/odd becomes XOR arithmetic.

Turn chains into paths

For a fixed prefix $1\ldots \ell$ , make a DAG:

vertex $i$ is chord $i$ ;
for $i<j$ , add edge $i\to j$ if the two chords intersect.

A chain is exactly a directed path in this DAG. Singletons are paths of length $0$ .

Let

$P_{i,j}=\text{parity of directed paths from }i\text{ to }j.$

Then $P_{i,i}=1$ , and $P_{i,j}=0$ for $i>j$ .

Also define

$L_j=\sum_i P_{i,j}$

as the parity of chains ending at $j$ , and

$R_i=\sum_j P_{i,j}$

as the parity of chains starting at $i$ .

A chain containing chord $i$ uniquely splits into a chain ending at $i$ and a chain starting at $i$ . So the parity of chains containing $i$ is

$L_iR_i.$

Therefore the prefix is tight-knit iff there is no $i$ with $L_i=1$ and $R_i=1$ .

The direct-toggle trap

When a new chord $x$ is appended, $L_x$ is easy:

$L_x=1+\sum_{j<x,\ j\sim x}L_j.$

Old $L$ values never change.

But old $R$ values are not toggled only for chords that directly intersect $x$ . That is fake-solution bait. An old chord $i$ gets new chains ending at $x$ through every path from $i$ into some chord that intersects $x$ .

If $u_j=1$ when old chord $j$ intersects $x$ , then the new contribution to $R_i$ is

$\sum_j P_{i,j}u_j.$

So we need to apply this transitive update without touching all chords.

Column vectors

For the proof, imagine every chord $i$ has a formal basis vector $e_i$ . Define the bad-set vector

$B=\sum_{i:L_i=1,\ R_i=1} e_i.$

The prefix is tight-knit iff $B=0$ .

Using $R_i=\sum_jP_{i,j}$ ,

=\sum_i L_i\left(\sum_jP_{i,j}\right)e_i =\sum_j\left(\sum_i L_iP_{i,j}e_i\right).$$ Define $$W_j=\sum_i L_iP_{i,j}e_i.$$ Then $$B=\bigoplus_j W_j.$$ This is the key trick. Instead of maintaining every $R_i$, maintain these column summaries $W_j$. **Inserting a chord** When chord $x$ is inserted, old columns do not change. Only the new column $x$ appears. For old $i$, $$P_{i,x}=\sum_{j<x}P_{i,j}u_j,$$ where $u_j=1$ iff chord $j$ intersects chord $x$. Therefore $$\sum_i L_iP_{i,x}e_i =\sum_i L_ie_i\sum_jP_{i,j}u_j =\sum_j u_j\left(\sum_i L_iP_{i,j}e_i\right) =\sum_{j:u_j=1}W_j.$$ Also $P_{x,x}=1$, so if $L_x=1$, the new chord contributes $e_x$ to $W_x$. Thus $$W_x=\left(\bigoplus_{j<x,\ j\sim x}W_j\right)\oplus ([L_x=1]e_x).$$ Then just do $$B\leftarrow B\oplus W_x.$$ The prefix is tight-knit iff $B=0$. **Circle geometry** For chords $(a,b)$ and $(c,d)$, they intersect iff exactly one endpoint of one chord lies strictly inside the other chord. So for a new chord $(a,b)$, old intersecting chords are exactly old chords with exactly one endpoint in $(a,b)$. Use Fenwick trees with XOR: - store $L_j$ at both endpoints of chord $j$; - store $W_j$ at both endpoints of chord $j$. A query on $[a+1,b-1]$ sees a chord zero times if both endpoints are outside, twice if both are inside, and once if exactly one endpoint is inside. Since we use XOR, the first two cases vanish and the crossing chords remain. Pretty slick, honestly. **Implementation detail** The formal vectors $e_i$ are too large to store, so the code replaces each $e_i$ by a random fingerprint: two `uint64_t` values plus one parity bit. This is the intended hashing/probability part. Collision probability is tiny enough that worrying about it is mostly competitive-programming cosplay. **Algorithm** For each chord $x=(a,b)$: 1. Query `fwL` on $[a+1,b-1]$ to get $s=\sum_{j<x,\ j\sim x}L_j$. 2. Set $L_x=1\oplus s$. 3. Query `fwW` on $[a+1,b-1]$ to get $C=\bigoplus_{j<x,\ j\sim x}W_j$. 4. Set $W_x=C\oplus([L_x=1]e_x)$. 5. Toggle $B\leftarrow B\oplus W_x$. 6. Insert $L_x$ into `fwL` at both endpoints if $L_x=1$. 7. Insert $W_x$ into `fwW` at both endpoints. 8. Output `1` iff $B=0$, otherwise `0`. **Correctness** Chains are exactly directed paths in the intersection DAG, so $L_i$ and $R_i$ are respectively the path parities ending and starting at $i$. Every chain containing $i$ decomposes uniquely through $i$, hence its parity is $L_iR_i$. Thus tight-knit means no chord has both values equal to $1$. The vector $B=\sum_iL_iR_ie_i$ is exactly the set of bad chords. Since $R_i=\sum_jP_{i,j}$, rewriting the sum by columns gives $B=\bigoplus_jW_j$. When inserting $x$, old columns stay unchanged. The new column satisfies $P_{i,x}=\sum_ju_jP_{i,j}$, so its old-chord contribution is exactly $\bigoplus_{j:u_j=1}W_j$. The chord $x$ itself contributes exactly when $L_x=1$. Therefore the computed $W_x$ is correct, and XORing it into $B$ keeps $B$ correct. The Fenwick queries return exactly the intersecting old chords because intersection is equivalent to exactly one endpoint lying inside the new chord interval. Therefore every step computes the same values as the formal DP, and the answer is correct up to the negligible hash-collision probability. **Complexity** Each chord uses $O(\log n)$ Fenwick work, so the total complexity is $O(n\log n)$ per test case and $O(n)$ memory.

deCH OR Dations

Progressive nudges

Full explanation

Generated C++